貪心

都選最好的

找零問題

/*
 * AP325
 * P-4-1. 少林寺的代幣
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
	int money[4] = {1,5,10,50};
	int n;
	cin >> n;
	for(int i=0;i<n;++i){
		int x;
		cin >> x;
		int cnt = 0;
		int j=3;
		while(x>0){
			if(x>=money[j]){
				x-=money[j];
				cnt+=1;
			}else{
				--j;
			}
		}
		cout << cnt << endl;
	}
}

最大值選擇問題

/*
 * NCOJ
 * 97. [Tutorial] 好吃的蛋糕
*/
#include<bits/stdc++.h>
using namespace std;

struct cmp{
    bool operator()(int a, int b) {
        return a < b;
    }
};
priority_queue<int, vector<int>, cmp> pq;

int main(){
    int n,m;
    cin >> n >> m;
    for(int i=0;i<n;++i){
        int x;
        cin >> x;
        pq.push(x);
    }
    long long sum = 0;
    while(m--){
        sum += pq.top();
        pq.pop();
    }
    cout << sum << endl;
}

最小化總完成時間

/*
 * NCOJ
 * 1072. A.誰先晚餐
*/
#include<bits/stdc++.h>
using namespace std;

struct Dish {
    int c;
    int e;
};

bool cmp(Dish a, Dish b) {
    return a.e > b.e;
}

int main(){
    int n;
    while(cin >> n){
        if(n==0){
            break;
        }
        vector<Dish>v(n);
        for(int i=0;i<n;++i){
            cin >> v[i].c >> v[i].e;
        }
        sort(v.begin(), v.end(), cmp);
        int ans = 0;
        int sum = 0;
        for(int i=0;i<n;++i){
            sum += v[i].c;
            ans = max(ans,sum+v[i].e);
        }
        cout << ans << endl;
    }
}

排程問題 (並行優先)

/*
 * zerojudge
 * b231. TOI2009 第三題：書
*/
#include<bits/stdc++.h>
using namespace std;

struct T{
    int t1;
    int t2;
};

bool cmp(T a,T b){
    return a.t2 > b.t2;
}

int main(){
    int n;
    while(cin >> n){
        vector<T>v(n);
        for(int i=0;i<n;++i){
            cin >> v[i].t1 >> v[i].t2;
        }
        sort(v.begin(),v.end(), cmp);
        int start = 0;
        int t = 0; 
        for(int i=0;i<n;++i){
            start += v[i].t1;
            t = max(t, start + v[i].t2);
        }
        cout << t << endl;
    }
}