[NOI2017] 蔬菜

前不久做了一道同样出处的题,然后发现这道也做了,居然还是黑题(很好写,但思路我想不到),就花了20分钟回顾了一下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,m,k,c[N],d[N],day[N],fa[N];
ll a[N],s[N],ans[N];
int g_fa(int u) {return fa[u]=(fa[u]==u)?u:g_fa(fa[u]);}
struct node {
	int x;ll w;
	bool operator<(const node &u) const{return w<u.w;}
};
priority_queue<node> Q;
int main() {
//	freopen("mm.in","r",stdin);
//	freopen("mm.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) scanf("%d%d%d%d",&a[i],&s[i],&c[i],&d[i]);
	for(int i=1;i<=n;i++) Q.push((node){i,s[i]+a[i]});
	for(int i=0;i<=1e6;i++)fa[i]=i;
	int cc=0;
	while(!Q.empty()) {
		int u=Q.top().x;ll w=Q.top().w; Q.pop();
		int dmx=1e6;
		if(d[u]) dmx=min(dmx,(c[u]+d[u]-1)/d[u]);
		dmx=g_fa(dmx);
		if(!dmx) continue;
		day[dmx]++;if(day[dmx]==m)fa[dmx]=g_fa(dmx-1);
		c[u]--;if(c[u])Q.push((node){u,a[u]});
		ans[cc+1]=ans[cc]+w;cc++;
	}
//	printf("%d\n",cc);
	for(int i=1;i<=k;i++) {
		int p; scanf("%d",&p);
		printf("%lld\n",ans[min(cc,p*m)]);
	} 
	return 0;
}
上一篇:day06 视图层


下一篇:Day 5 位运算符