526互联

3.3 贪心 参考代码

发布时间 2023-07-25 15:28:31作者: RonChen

P3742 umi的函数

#include <cstdio>
char x[105], y[105];
int main()
{
    int n;
    scanf("%d%s%s", &n, x, y);
    bool ok = true;
    for (int i = 0; i < n; i++) {
        if (x[i] < y[i]) {
            ok = false;
            break;
        }
    }
    if (ok) printf("%s\n", y);
    else printf("-1\n");
    return 0;
}

P2240 [深基12.例1] 部分背包问题

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 105;
struct Coin {
    int m, v;
};
Coin a[MAXN];
bool cmp(const Coin& lhs, const Coin& rhs) {
    return rhs.m * lhs.v > lhs.m * rhs.v;
}
int main()
{
    int n, t;
    scanf("%d%d", &n, &t);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a[i].m, &a[i].v);
    }
    sort(a, a + n, cmp);
    double ans = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i].m < t) {
            ans += a[i].v;
            t -= a[i].m;
        } else {
            ans += 1.0 * a[i].v / a[i].m * t;
            break;
        }
    }
    printf("%.2f\n", ans);
    return 0;	
}
  • 如果在第 26 行输出答案，则存在一个漏洞：当所有金币都取完而背包还未装满，程序就会没有输出结果

P1223 排队接水

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
struct S {
    int t, idx;
};
S a[MAXN];
bool cmp(const S& lhs, const S& rhs) {
    if (lhs.t != rhs.t) return lhs.t < rhs.t;
        else return lhs.idx < rhs.idx;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i].t);
        a[i].idx = i + 1;
    }
    sort(a, a + n, cmp);
    double sum = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
        printf("%d%s", a[i].idx, i + 1 == n ? "\n" : " ");
        ans += sum;
        sum += a[i].t;
    }
    printf("%.2f\n", ans / n);
    return 0;
}

P1803 凌乱的yyy / 线段覆盖

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
struct Contest {
    int bg, ed;
};
Contest a[MAXN];
bool cmp(const Contest& lhs, const Contest& rhs) {
    return lhs.ed < rhs.ed;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d%d", &a[i].bg, &a[i].ed);
    sort(a, a + n, cmp);
    int ans = 0;
    int cur = -1;
    for (int i = 0; i < n; ++i)
        if (a[i].bg >= cur) {
            cur = a[i].ed;
            ++ans;
        }
    printf("%d\n", ans);
    return 0;
}

P3817 小A的糖果

#include <cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
LL a[MAXN];
int main()
{
    int n, x;
    scanf("%d%d", &n, &x);
    for (int i = 0; i < n; ++i) scanf("%lld", &a[i]);
    LL ans = 0;
    // 如果一盒糖果本身数量就超限，先吃到x
    if (a[0] >= x) {
        ans += a[0] - x;
        a[0] = x;
    }
    for (int i = 1; i < n; ++i) {
        if (a[i] + a[i - 1] > x) {
            LL r = a[i] + a[i - 1] - x;
            if (r <= a[i]) {
                ans += r;
                a[i] -= r;
            } else {
                ans += a[i];
                r -= a[i];
                a[i] = 0;
                ans += r;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}
  • 贪心策略：尽量减少处在中间的盒子的糖果，这样对左右两个相邻的盒子都有好处，在基于这一策略的前提下，要考虑到第一盒糖果的特殊性（有可能单个盒子中糖果数量已经超出限制）

P1478 陶陶摘苹果（升级版）

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 5005;
struct Apple {
    int x, y;
};
Apple apple[MAXN];
bool cmp(const Apple& lhs, const Apple& rhs) {
    return lhs.y < rhs.y;
}
int main()
{
    int n, s, a, b, cnt = 0;
    scanf("%d%d%d%d", &n, &s, &a, &b);
    for (int i = 0; i < n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x <= a + b) {
            apple[cnt].x = x;
            apple[cnt].y = y;
            ++cnt;
        }
    }
    sort(apple, apple + cnt, cmp);
    int ans = 0;
    for (int i = 0; i < cnt; ++i) 
        if (s >= apple[i].y) {
            ++ans;
            s -= apple[i].y;
        } else break;
    printf("%d\n", ans);
    return 0;
}

P5019 [NOIP2018 提高组] 铺设道路

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
int d[MAXN];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &d[i]);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += max(d[i] - d[i - 1], 0);
    }
    printf("%d\n", ans);
    return 0;
}

P1208 [USACO1.3] 混合牛奶 Mixing Milk

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 200005;
struct Milk {
    int p, w;
};
bool cmp(const Milk& lhs, const Milk& rhs) {
    return lhs.p != rhs.p ? lhs.p < rhs.p : lhs.w > rhs.w;
}
Milk a[MAXN];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a[i].p, &a[i].w);
    }
    sort(a, a + m, cmp);
    LL ans = 0;
    for (int i = 0; i < m; ++i) {
        if (a[i].w < n) {
            ans += a[i].p * a[i].w;
            n -= a[i].w;
        } else {
            ans += n * a[i].p;
            break;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

P1094 [NOIP2007 普及组] 纪念品分组

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 30005;
int a[MAXN];
int main()
{
    int w;
    scanf("%d", &w);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    sort(a, a + n);
    int l = 0, r = n - 1;
    int ans = 0;
    while (l <= r) {
        if (l == r) {
            ++ans;
            break;
        } else {
            if (a[l] + a[r] <= w) ++l;
            --r;
            ++ans;
        }
    }
    printf("%d\n", ans);
    return 0;
}

P4995 跳跳！

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 305;
int h[MAXN];
int main()
{

    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &h[i]);
    sort(h + 1, h + n + 1);
    int p = 0, q = n;
    int i = 0;
    LL ans = 0;
    while (p < q) {
        ans += (h[q] - h[p]) * (h[q] - h[p]);
        if (i % 2 == 0) p++;
            else q--;
        ++i;
    }
    printf("%lld\n", ans);
    return 0;
}