网站注册转化率,甘肃网站建设专家,域名是否就是网站,做交通锁具网站Acwing 277. 饼干
题意#xff1a;
圣诞老人共有 M 个饼干#xff0c;准备全部分给 N 个孩子。
每个孩子有一个贪婪度#xff0c;第 i 个孩子的贪婪度为 g[i]。
如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多#xff0c;那么第 i 个孩子会产生 g[i]a[i] 的怨气。
给…Acwing 277. 饼干
题意
圣诞老人共有 M 个饼干准备全部分给 N 个孩子。
每个孩子有一个贪婪度第 i 个孩子的贪婪度为 g[i]。
如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多那么第 i 个孩子会产生 g[i]×a[i] 的怨气。
给定 N、M 和序列 g圣诞老人请你帮他安排一种分配方式使得每个孩子至少分到一块饼干并且所有孩子的怨气总和最小。 1≤N≤30, N≤M≤5000, 1≤gi≤10710^7107
题解
一个孩子的怨气大小与其他孩子获得的饼干数有关通过贪心分析不难发现贪婪度大的孩子应该分到更多的饼干(也可以证明此处略) 所以我们把N个孩子按照贪婪值从大到小排序他们分配到的饼干数将是单调递减的
代码
在代码中是枚举分到饼干数量为1的人数
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
using namespace std;
typedef long long ll;
typedef pairint, int PII;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
void rd_txt(){#ifdef ONLINE_JUDGE#elsefreopen(in.txt,r,stdin);#endif
}
const int N 31, M 5010;int n, m;
PII g[N];
int s[N];
int f[N][M];
int ans[N];int main()
{cin n m;for (int i 1; i n; i ){cin g[i].first;g[i].second i;}sort(g 1, g n 1);reverse(g 1, g n 1);//现在g是从大到小 for (int i 1; i n; i ) s[i] s[i - 1] g[i].first;memset(f, 0x3f, sizeof f);f[0][0] 0;for (int i 1; i n; i )for (int j 1; j m; j ){if (j i) f[i][j] f[i][j - i];for (int k 1; k i k j; k )//枚举的k是数量为1的人 f[i][j] min(f[i][j], f[i - k][j - k] (s[i] - s[i - k]) * (i - k));}cout f[n][m] endl;//根据结果反着推过程 int i n, j m, h 0;while (i j){if (j i f[i][j] f[i][j - i]) j - i, h ;else{for (int k 1; k i k j; k )if (f[i][j] f[i - k][j - k] (s[i] - s[i - k]) * (i - k)){for (int u i; u i - k; u -- )ans[g[u].second] 1 h;i - k, j - k;break;}}}for (int i 1; i n; i ) cout ans[i] ;cout endl;return 0;
}
