2019.7.16 义乌模拟赛 T4 老鼠进洞
2021/7/17 6:35:16
本文主要是介绍2019.7.16 义乌模拟赛 T4 老鼠进洞,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
很妙的一道题。
首先我们考虑将所有老鼠都进左边能进的且最优的洞。
然后有些老鼠其实是可以反悔的去选右边的洞,如果设第\(i\)只老鼠原来连\(j\),反悔去连\(k\),那么对答案的贡献就是\(p_k-2x_i+p_j\)
可以发现这个东西对\(k\)独立,那么我们用一个堆维护即可。
但是一个洞也可以反悔不去选那个老鼠,这样我们对洞也建一个堆这样维护即可。时间复杂度\(O(nlogn)\)
code:
#include<bits/stdc++.h> #define I inline #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define abs(x) ((x)>0?(x):-(x)) #define re register #define ll long long #define db double #define N 1000000 #define M 5000 #define mod 1000000000 #define eps (1e-7) #define U unsigned int #define it iterator #define Gc() getchar() #define Me(x,y) memset(x,y,sizeof(x)) using namespace std; int n,m,k,cnt,pus;ll ans,tot; I void read(int &x){ char s=Gc();x=0;int f=1;while(s<'0'||s>'9')s=='-'&&(f=-1),s=Gc(); while(s>='0'&&s<='9') x=x*10+s-48,s=Gc();x*=f; } struct yyy{int w,c;}S[N+5];I bool cmp(yyy x,yyy y){return x.w<y.w;} struct ques{int w,flow;bool operator <(const ques &s)const{return w>s.w;};}now; priority_queue<ll,vector<ll>,greater<ll> > Q1;priority_queue<ques> Q2; int main(){ freopen("mice.in","r",stdin);freopen("mice.out","w",stdout); re int i;read(n);read(m);k=n+m;for(i=1;i<=n;i++) scanf("%d",&S[++cnt].w),S[cnt].c=-1;for(i=1;i<=m;i++) ++cnt,read(S[cnt].w),read(S[cnt].c),tot+=S[cnt].c; if(tot<n) return printf("-1\n"),0;sort(S+1,S+cnt+1,cmp);for(i=1;i<=cnt;i++){ if(~S[i].c){ while(!Q1.empty()&&S[i].c&&Q1.top()+S[i].w<0)tot=Q1.top()+S[i].w,Q1.pop(),ans+=tot,Q2.push((ques){-S[i].w-tot,1}),S[i].c--; S[i].c&&(Q2.push((ques){-S[i].w,S[i].c}),0); } else{ tot=1e14;if(!Q2.empty())now=Q2.top(),tot=now.w+S[i].w,Q2.pop(),now.flow--,now.flow&&(Q2.push(now),0);ans+=tot,Q1.push(-tot-S[i].w); } }printf("%lld\n",ans); }
这篇关于2019.7.16 义乌模拟赛 T4 老鼠进洞的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性