Acwing 277. 餅干

題意：

圣誕老人共有 M 個(gè)餅干，準(zhǔn)備全部分給 N 個(gè)孩子。

每個(gè)孩子有一個(gè)貪婪度，第 i 個(gè)孩子的貪婪度為 g[i]。

如果有 a[i] 個(gè)孩子拿到的餅干數(shù)比第 i 個(gè)孩子多，那么第 i 個(gè)孩子會(huì)產(chǎn)生 g[i]×a[i] 的怨氣。

給定 N、M 和序列 g，圣誕老人請(qǐng)你幫他安排一種分配方式，使得每個(gè)孩子至少分到一塊餅干，并且所有孩子的怨氣總和最小。
1≤N≤30,
N≤M≤5000,
1≤gi≤$10^7$

題解：

一個(gè)孩子的怨氣大小與其他孩子獲得的餅干數(shù)有關(guān)，通過(guò)貪心分析不難發(fā)現(xiàn)，貪婪度大的孩子應(yīng)該分到更多的餅干(也可以證明，此處略)
所以我們把N個(gè)孩子按照貪婪值從大到小排序，他們分配到的餅干數(shù)將是單調(diào)遞減的

代碼：

在代碼中是枚舉分到餅干數(shù)量為1的人數(shù)

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); using namespace std; typedef long long ll; typedef pair<int, int> PII; //Fe~Jozky const ll INF_ll=1e18; const int INF_int=0x3f3f3f3f; inline ll read(){ll s=0,w=1ll;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1ll;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10ll+((ch-'0')*1ll),ch=getchar();//s=(s<<3)+(s<<1)+(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);//現(xiàn)在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是數(shù)量為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;//根據(jù)結(jié)果反著推過(guò)程 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; }

總結(jié)

以上是生活随笔為你收集整理的Acwing 277. 饼干的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。