욕심~

예제1: TZU 1004(연자경마) 직접 보기 코드:

#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=1010;
int n,a[MAX],b[MAX];
int main()
{   while(cin>>n&&n)
    {   int i,j,sum,num;//sum       ,num        
        for(i=0;i<n;i++) cin>>a[i];
        for(i=0;i<n;i++) cin>>b[i]; 
        j=sum=num=0;
        sort(a,a+n);
        sort(b,b+n);
        for(i=0;i<n;i++)
        {  if(a[i]>b[j]) sum++,j++;//                ,        
           if(a[i]<=b[j]&&a[i]<b[n-j-1]) num++;//             ,   ~ 
        }
        cout<<(sum>num?"YES":"NO")<<endl;
    }
    return 0;
}

예제2: NYOJ 218(다중기 스케줄링 문제), 욕심 알고리즘--NP 완전 문제, 두 가지 상황으로 나뉜다.
①、n<=m일 때 가장 긴 시간을 직접 출력하면 된다.
②、n>m의 경우 시간의 길이에 따라 작은 것부터 큰 것까지 정렬(큰 것부터 작은 것까지 정렬 가능), 가장 큰 것부터 배열에 저장한다. 어느 것이 가장 먼저 완성되면 안배되지 않은 일의 시간까지 모든 일이 이미 완성된 후에 가장 긴 시간을 출력한다.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX=10010;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
int num,n,m,Time[MAX],total[MAX];
int main()
{   scanf("%d",&num);
    while(num--)
    {   CLR(total,0);
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            scanf("%d",&Time[i]);
        sort(Time,Time+n);
        if(n<=m) printf("%d
",Time[n-1]); 
        else
        {   for(int i=n-1,j=0;i>=n-m;i--)
                total[j++]=Time[i];
            for(int i=n-m-1;i>=0;i--)
            {   int pos=0,min=total[0];
                for(int j=0;j<m;j++)
                    if(total[j]<min) min=total[j],pos=j;
                total[pos]+=Time[i];    
            }         
            sort(total,total+m);
            printf("%d
",total[m-1]);
        }
    }
    return 0;
}

예제3: NYOJ 351(외나무배에서의 여행). 뒤에 토론에서 정신은 이것이 NP문제라고 말했다. 모르면 욕심을 부리고 가장 큰 안배부터 하면 된다. 복잡한지 모르겠다. 개인적인 느낌은 다음과 같다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=310;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
int num,maxt,n,wg[MAX],visit[MAX];
int main()
{   scanf("%d",&num);
    while(num--)
    {   CLR(visit,0);
        scanf("%d%d",&maxt,&n);
        for(int i=0;i<n;i++)
            scanf("%d",&wg[i]);
        sort(wg,wg+n);
        int sum=0,total;
        for(int i=n-1;i>=0;i--)    
        {   total=0;
            if(!visit[i])
            {   total+=wg[i];
                visit[i]=1;
                for(int j=i-1;j>=0;j--)
                    if(!visit[j]&&total+wg[j]<=maxt)
                    {   total+=wg[j];
                        visit[j]=1;
                    }
                sum++;    
            }
        }
        printf("%d
",sum);
    }
    return 0;
}

예제4:NYOJ287(레이더 설치), 앞의 분수장치와 같은 제목으로 방식만 바꿨다.분수장치 코드는 여기 있습니다.

#include<iostream>
#include<cmath>
#include<cstring>
#include<vector>
#include<iterator> 
#include<algorithm>
using namespace std;
const int MAX=1010;
#define exp 1e-6 
#define CLR(arr,val) memset(arr,val,sizeof(arr))
int num,total=1,visit[MAX],sum;
double D;
class Point{
public:
    Point(){x=y=0;}
    Point(int L,int R):x(y),y(R){}
    friend istream& operator>>(istream &input,Point &P) 
    {   input>>P.x>>P.y;
        return input;
    }  
    double Dis() const 
    {   double dis=D*D-y*y;
        if(dis>=0) return sqrt(dis);
        return -1;
    }   
    double Right() const {return x+Dis();}
    double Left() const {return x-Dis();}
private:
    double x,y;       
};
struct mysort
{   bool operator()(const Point &P1,const Point &P2)
    {   return P1.Right()<P2.Right();
    }
};
int main()
{   Point P;
    while(cin>>num>>D,num+D)
    {   int sum=0;
        CLR(visit,0);
        bool flag=true;
        vector<Point> v;
        for(int i=0;i<num;i++)
        {   cin>>P;
            if(P.Dis()==-1) flag=false;  
            v.push_back(P); 
        }    
        cout<<"Case "<<total++<<": ";
        if(!flag) cout<<-1<<endl;
        else 
        {   sort(v.begin(),v.end(),mysort());
            for(vector<Point>::size_type i=0;i<v.size();i++)
                if(!visit[i])
                {   visit[i]=1;
                    sum++;
                    for(vector<Point>::size_type j=i+1;j<v.size();j++)
                        if(!visit[j]&&v[j].Left()-v[i].Right()<=exp)
                            visit[j]=1;  
                }  
            cout<<sum<<endl;
        }
    } 
    return 0;
}