蜂巢黄瓜 hg5 3966 黄瓜
https://www.lydsy.com/JudgeOnline/problem.php?id=4946
https://www.luogu.org/problemnew/show/P3826
http://uoj.ac/problem/318
题意看原题……
不得不说是一道十分妙的题,辛酸史放在后面讲。
参考:noi2017知乎上lzz的题解,洛谷上唯一一篇题解。
lzz的算法不太好理解啊……于是copy的洛谷题解。
看到如此乱七八糟的题目限制很容易想到费用流,但是数据范围告诉我们显然不可以网络流。
有着众多解题经验的我们得知:万物皆网络流,网络流皆贪心。
先思考网络流怎么建,一种可行方案为将时间从P~1连边,每个时间向T连m容量边,S向每种水果每个变质时间连变质水果数量。
实际上我们把时间倒序之后就变成了有多少水果会在第几天出现,并且永远不腐。
再考虑每天也就能拿m个,贪心来讲反正后面水果也不腐,不拿白不拿,直接把当天所有水果挑选最贵的m个卖了即可。
于是我们不难求出时间为P的答案——通过一个优先队列。
但是显然以这种速度处理所有的询问是不可取的,思考有没有一种推法能够将ans[P]推到ans[P-1]去呢?
显然是有的,思考时间的提前会将原本在P运来的水果提前至P-1天运来,于是这P-1天的可选水果并没有变,对前P-1天唯一的变化就是我们可以用贵水果替换掉便宜水果,因此剩下来卖不了的水果一定是原本选择的水果中最便宜的几个。
继续优先队列将我们选过的水果放里面,弹出最小的几个使得我们选的水果数量为(P-1)*m即可。
总结就是一道好题,思维含量巨大,代码实现比较简单,洛谷评为黑题也没有任何问题。
#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int P=1e5;
inline ll read(){
ll X=0,w=0;char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
struct veg{
ll v;int i;
};
struct cmp1{
bool operator ()(veg a,veg b){return a.v<b.v;}
};
struct cmp2{
bool operator ()(veg a,veg b){return a.v>b.v;}
};
priority_queue<veg,vector<veg>,cmp1>q;
priority_queue<veg,vector<veg>,cmp2>p;
queue<veg>tmp;
ll a[N],s[N],c[N],x[N],g[N],ans[P+5],tot;
int n,m,k;
vector<int>sold[P+5];
int main(){
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++){
a[i]=read(),s[i]=read(),c[i]=read(),x[i]=read();
if(x[i])sold[min((ll)P,(c[i]+x[i]-1)/x[i])].push_back(i);
else sold[P].push_back(i);
}
for(int i=P;i>=1;i--){
for(int j=0;j<sold[i].size();j++){
q.push((veg){a[sold[i][j]]+s[sold[i][j]],sold[i][j]});
}
ll lim=m;
while(lim&&!q.empty()){
veg f=q.top();q.pop();
if(!g[f.i]){
ans[P]+=f.v;g[f.i]++;lim--;
if(g[f.i]<c[f.i])q.push((veg){a[f.i],f.i});
}else{
ll delta=min((ll)lim,c[f.i]-g[f.i]-(i-1)*x[f.i]);
ans[P]+=delta*f.v;g[f.i]+=delta;lim-=delta;
if(g[f.i]<c[f.i])tmp.push((veg){a[f.i],f.i});
}
}
while(!tmp.empty()){
q.push(tmp.front());tmp.pop();
}
}
for(int i=1;i<=n;i++){
if(g[i]==1)p.push((veg){s[i]+a[i],i});
else if(g[i])p.push((veg){a[i],i});
tot+=g[i];
}
for(int i=P-1;i>=1;i--){
ans[i]=ans[i+1];
if(tot<=m*i)continue;
ll lim=tot-m*i;
while(lim&&!p.empty()){
veg f=p.top();p.pop();
if(g[f.i]!=1){
ll delta=min((ll)lim,g[f.i]-1);
ans[i]-=delta*f.v;g[f.i]-=delta;lim-=delta;
if(g[f.i]==1)p.push((veg){a[f.i]+s[f.i],f.i});
else p.push((veg){a[f.i],f.i});
}else{
lim--;g[f.i]--;ans[i]-=f.v;
}
}
tot=m*i;
}
for(int i=1;i<=k;i++)printf("%lld\n",ans[read()]);
return 0;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者:luyouqi233。 +
+欢迎访问我的博客: +
+++++++++++++++++++++++++++++++++++++++++++
推荐阅读