C 언어 욕심(3)최소 차단 시스템(Hdu 1257)

Problem Description
어떤 나라는 적국의 미사일 공격을 방어하기 위해 미사일 차단 시스템을 발전시켰다.그러나 이런 미사일 차단 시스템은 결함이 하나 있다. 비록 그의 첫 번째 포탄은 임의의 고도에 도달할 수 있지만, 이후의 모든 포탄은 앞의 포탄의 높이를 초과할 수 없다.어느 날, 레이더가 적국의 미사일의 습격을 포착했다.이 시스템은 아직 시험 단계에 있기 때문에 단지 하나의 시스템만 있기 때문에 모든 미사일을 차단할 수 없을 것이다.어떡하지?몇 가지 시스템을 더 만들지!네가 말하는 것은 아주 쉬운데, 원가는?원가가 큰 문제야.그래서 제가 이곳에 와서 구조를 요청했습니다. 최소한 몇 세트의 차단 시스템이 필요한지 계산해 주세요.
 
Input
여러 그룹 데이터를 입력합니다.각 조의 데이터는 미사일 총 개수(정수), 미사일이 날아오는 높이(레이더가 제시한 고도 데이터는 30000보다 크지 않은 정수, 빈칸으로 구분)를 포함한다.
 
Output
각 조의 데이터 출력에 대응하여 모든 미사일을 차단하려면 최소한 몇 세트의 이런 미사일 차단 시스템을 갖추어야 한다.
 
Sample Input

   
   
   
   

    
    
    
    8 389 207 155 300 299 170 158 65
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    2
   
   
   
   

 
이 문제는 욕심 문제다.구체적인 욕심 과정은 매번 미사일 고도를 읽을 때마다 포가 차단할 수 있는지 판단하고 없으면 차단 시스템을 추가해야 한다. 차단할 수 있다면 현재 고도와 목표 미사일 고도의 차이가 가장 적은 것을 선택해야 한다.이렇게 해야만 고도의 손실을 최소화할 수 있다.다시 말하면 현재 3개의 차단 시스템이 있는데 현재의 최고 높이는 각각 100, 90, 80이다. 현재 85의 포탄을 차단하려면 100과 90에서 하나를 선택해야 한다. 90과 85의 차이가 비교적 가깝고 고도 손실이 적기 때문에 90의 이 차단 시스템을 선택하여 차단한다.구체적인 코드는 사고방식을 실현한다. 하나의 수조 f[]로 현재의 차단 시스템 개수가 이미 각각의 현재 차단 높이를 나타낸다.처음에는 단 하나, 차단고도는 자연히 첫 번째 미사일의 타격고도였고, 그 다음에 매번 한 미사일의 타격고도 H를 읽는다.그리고 f[]수조에서 왼쪽 f[0]부터 위치를 찾아 i로 하여금 f[i]>H>f[i-1]를 물론 f[0]가 H보다 크면 i는 자연히 0이 된다. 현재 i의 차단 시스템은 고도의 손실을 최소화할 수 있는 차단 시스템이라는 것을 설명하고 이 차단 시스템의 높이를 H로 바꾸면 현재 차단 시스템이 H의 이 미사일을 차단하고 있음을 나타낸다.만약에 상식을 만족시키는 이 위치를 찾지 못했다면 i설은 현재 H가 모든 차단 시스템의 차단 높이를 초과했다면 우리는 차단 시스템을 하나 더 가입해야 한다. 그리고 이 차단 시스템의 차단 높이를 H로 바꾸어 f[]에 가입해야 한다. 마지막으로 H라는 미사일을 차단했다고 밝혔다.
중요:
i 위치를 찾을 때 사용:
2분 찾기!!

#include <stdio.h>
#include <algorithm>
using namespace std;
#include <stdio.h>
int main()
{
    int f[100000];
    int i,a,n,t=0;
    int l,r,mid;
    while(scanf("%d",&n)!=EOF)
    {
        t=1;
        while(n--)
        {
            scanf("%d",&a);
            l=0,r=t;
            while(l<=r)         //    
            {
                mid=(l+r)/2;    
                if(f[mid]==a)
                {
                    l=mid;
                    break;
                }
                else if(f[mid]<=a)
                    l=mid+1;
                else
                    r=mid-1;
            }
            if(l<t)
                f[l]=a;
            else
                f[t++]=a;
        }
        printf("%d
",t-1);
    }
    return 0;
}