0%

贪心法

发表于 更新于
挑战程序设计竞赛(Programing Contest Challenge Book)

贪心法指遵循某种规则，不断贪心地选取当前最优策略的算法设计方法。

硬币问题

有1元，5元，10元，50元，100元，500元硬币各$C_{1},C_{5},C_{10},C_{50},C_{100},C_{500}$枚.现在用这些硬币支付A元，最少需要多少枚硬币？假定至少有一种支付方案。

1
2
3
4
5
6
7
8
9
10
11
12
int C[6] = {1, 5, 10, 50, 100, 500};
int V[6];//V[0] = C_1; V[1] = C_5;
int A;
void solve() {
    int res = 0;
    for (int i = 5; 0 <= i; i--){
        int t = min(A/C[i], V[i]);
        res += t;
        A -= t * C[i];
    }
    printf("%d\n", res);
}

区间问题

有n项工作，每项工作分别在$s_{1}$时间开始，在$t_{1}$时间结束。可以选择参与与否，如果选择参与，那么自始至终必须全程参与。此外，参与工作的时间段不能重合(开始和结束的瞬间也不允许)你的目标是尽可能多地参与工作， 最多能参与多少工作？

  • 每次可选的工作中，选结束时间最早的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int MAX_N = 100000;
int N, S[MAX_N], T[MAX_N];

pair<int , int> itv[MAX_N];

void solve() {
    for (int i = 0; i < N; i++) {
        itv[i].second = S[i];
        itv[i].first = T[i];
    }
    sort(itv, itv + N);
    int t = 0, ans = 0;
    for (int i = 0; i < N; i++) {
        if(itv[i].second > t) {
            ans ++;
            t = itv[i].first;
        }
    }
    printf("%d\n", ans);
}