BZOJ2793: [Poi2012]Vouchers

2019-11-08 02:56:42

字体：大中小

来源：转载

供稿：网友

调和级数：∑ni=1ni $/sum_{i=1}^n/frac n i$ 是nlogn $nlogn$ 级别的所以对于每个x，记录当前拿到了哪里，每组人来直接拿因为拿到10^6就可以不拿了，所以不会很慢时间复杂度O(nlogn)

code：

#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long long#define lowbit(x) x&(-x)using namespace std;void read(int &x){ char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';}const int maxn = 1001000;int n,m;int head[maxn],v[maxn];bool vi[maxn];ll ans[maxn],an;int main(){ read(m); for(int i=1;i<=m;i++) { int x; read(x); v[x]=1; } for(int i=1;i<maxn;i++) head[i]=i; read(n); ll id=0; an=0; for(int i=1;i<=n;i++) { int x; read(x); int k=head[x]; int ti=x; while(k<maxn&&ti) { if(vi[k]) k+=x; else { id++; ti--; vi[k]=true; while(v[k]--) ans[++an]=id; } } head[x]=k; id+=(ll)ti; } PRintf("%lld/n",an); for(int i=1;i<=an;i++) printf("%lld/n",ans[i]); return 0;}

上一篇：html常用标签

下一篇：Beehive UVALive - 7528