题目链接

bzoj4946: [Noi2017]蔬菜

题解

挺神的贪心 把第次买的蔬菜拆出来，记下每种蔬菜到期的日期，填第一单位蔬菜比其他的要晚 按价格排序后，贪心的往前面可以填的位置填就可以了。找可以填的位置用并查集维护一下。这样就求出了最大天数的答案。 对于询问的答案，从最后一天往前推，把最便宜的那些丢掉就好了。

代码

#include<cstdio> #include<cstring> #include<algorithm> #define gc getchar #define pc putchar #define int long long inline int read() { int x = 0,f = 1; char c = getchar(); while(c < '0' || c > '9') c = gc(); while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc(); return x * f; } void print(int x) { if(x < 0) { pc('-'); x = -x; } if(x >= 10)print(x / 10); pc(x % 10 + '0'); } const int maxn = 200007; int n,m,k; struct node { int a,d,c,x; node(int a = 0,int c = 0,int x = 0,int d = 0) : a(a), c(c),x(x),d(d) {}; bool operator < (const node &k) const { return a > k.a; } } a[maxn]; int tot = 0; int q[maxn],fa[maxn]; int find(int x ) { if(fa[x] != x) fa[x] = find(fa[x]); return fa[x]; } void unionn(int x,int y) { int fx = find(x),fy = find(y); if(fx == fy) return ; fa[fy] = fx; } int cnt = 0; int g[maxn],d[maxn],ga[maxn]; int sum = 0; void calc(int idx,int c,int a) { sum += 1ll * c * a; g[cnt] += c;ga[cnt] = a; d[idx] += c; if(d[idx] == m) unionn(idx - 1,idx); } int L[maxn],upd[maxn]; int ans[maxn]; main() { //freopen("1.in","r",stdin); n = read(),m = read(),k = read(); for(int aa,s,c,x,i = 1;i <= n;++ i) { aa = read(),s = read(),c = read(),x = read(); a[++ tot] = node(aa + s,1,0,x ? (c - 1) / x + 1 : maxn - 7); if(-- c) a[++ tot] = node(aa,c,x,x ? (c - 1) / x + 1 : maxn - 7); } int maxd = 0; for(int i = 1;i <= k;++ i) maxd = std::max(maxd,q[i] = read()); std::sort(a + 1,a + tot + 1); for(int i = 1;i <= maxd;++ i) fa[i] = i; for(int i = 1;i <= tot;++ i) { cnt ++; int idx = find(std::min(a[i].d,maxd)); //a 价值 d GG日期 d 数量 x 每天GG数 int res = (idx - 1) * a[i].x ,now = a[i].c - res; while(idx && now) { int mn = std::min(m - d[idx],now); calc(idx,mn,a[i].a); now -= mn; int p = idx; idx = find(idx - 1); p -= idx; if(res) now += p * a[i].x , res -= p * a[i].x; } if(!find(maxd)) break ; } int R = 0; for(int i = 1;i <= maxd;++ i) L[i] = m - d[i] + L[i - 1]; for(int i = maxd;i;-- i) upd[i] = std::max(R - L[i],0ll),R += d[i]; for(int i = maxd;i >= 1;-- i) { ans[i] = sum; int tmp = upd[i - 1] - upd[i]; while(tmp) { int mn = std::min(tmp,g[cnt]); sum -= 1ll * ga[cnt] * mn; tmp -= mn; g[cnt] -= mn; if(!g[cnt]) -- cnt; } } for(int i = 1;i <= k;++ i) print(ans[q[i]]),pc('\n');// print(10); return 0; } // 1110001

转载于:https://www.cnblogs.com/sssy/p/9671586.html