AcWing 2025. 奶牛优惠卷
原题链接
困难
作者:
kimmmm
,
2022-06-12 02:00:46
,
所有人可见
,
阅读 231
巧妙的贪心
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, k, cnt;
LL m;
bool st[N];
struct node{
int price, tag, id;
}ns[N];
bool cmp (node a,node b)
{
if (a.price != b.price) return a.price < b.price;
else return a.tag < b.tag;
}
int main()
{
cin >> n >> k >> m;
for (int i = 1; i <= n; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
ns[++ cnt] = {a, 1, i};
ns[++ cnt] = {b, 2, i};
}
sort(ns + 1, ns + cnt + 1, cmp);
int ans = 0;
for (int i = 1; i <= cnt; i ++)
{
LL a = ns[i].price;
int b = ns[i].tag;
int c = ns[i].id;
if (m < a) break;
if (st[c] ||(k == 0 && b == 2)) continue;
st[c] = 1;
m -= a, ans ++;
if (b == 2) k --;
}
printf("%d", ans);
return 0;
}
题解是错的(更新数据了)
y1s1这不能算作好的题解
nnz
你nnz