求助,大佬求调。
查看原帖
求助,大佬求调。
602013
18974918693mzx楼主2023/1/14 11:38

这个贪心哪错了???

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int kMaxN = 5e4 + 5;

struct node {
    int p, c, cha;
}a[kMaxN];

int cmp1(node x, node y) {
    return x.cha < y.cha;
}

int n, m, k, cnt, ans, b[kMaxN], sum;

struct edge {
	int b;
	bool flag;
}q[kMaxN];

int cmp2(edge x, edge y) {
	return x.b < y.b;
}

signed main() {
    cin >> n >> k >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i].p >> a[i].c;
        a[i].cha = a[i].p - a[i].c;
    }
    sort(a + 1, a + n + 1, cmp1);
    for (int i = 1; i <= n && m && cnt <= k; i ++,cnt ++) {
        m -= a[i].cha;
        q[i].flag = 1;
        ans ++;
    }
    for (int i = 1; i <= n; i ++) {
    	if (!q[i].flag) {
    		q[++ sum].b = a[i].p;
    	}
    }
    sort(q + 1, q + sum + 1, cmp2);
    for (int i = 1; i <= sum && m; i ++) {
        m -= q[i].b;
        ans ++;
        if (m < 0) {
            ans --;
        }
    }
    cout << ans;
    return 0;
}
2023/1/14 11:38
加载中...