题目
你有\(n\)个士兵，需要将他们分成\(m\)组，每组可以为0；
现在这些士兵要去攻打\(m\)个敌人，每个敌人的生命值为\(hp_i\) ；
一轮游戏中一组士兵选定一个攻打的敌人，敌人生命值-=这组的人数；
胜利的判定是所有敌人的生命值为非正的；
输出胜利的最小轮数，可以达到最小轮数的分配方式，并输出每轮的策略；
\(1 \le m \le n \le 10^6 \ , \ 1 \le \sum hp_i \le 10^6\) ;
题解
答案的下界是\(\lceil \frac{\sum_{i=1}^{m} \ hp_i} n \rceil\) ，考虑构造这个下界;
注意到所有的和为\(n\)，首先让 $ hp_i $ 对 $ n $ 取模；
只需要构造
\[ \begin{cases} s_i &= (\sum_{j=1}^{i} hp_j) \ mod \ n &i \lt m \\ s_i &= n &i = m \\ \end{cases} \]排序得到\(s_1,\cdots,s_{m-1},s_m\)，构造\(s_i-s_{i-1}\)即可；
容易知道只有最后一次的\(n\)没有被充分利用，所以满足下界；
再 \(for\) 一遍模拟取模的过程求出策略即可；
#include #define mk make_pair#define fi first#define se second#define pb push_backusing namespace std;const int N=1000010;int n,m,a[N],pos[N],cnt;pair b[N];vector ans[N];char gc(){ static char*p1,*p2,s[1000000]; if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); return(p1==p2)?EOF:*p1++;}int rd(){ int x=0;char c=gc(); while(c<'0'||c>'9')c=gc(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc(); return x;}char ps[1000000],*pp=ps;void flush(){ fwrite(ps,1,pp-ps,stdout); pp=ps;}void push(char x){ if(pp==ps+1000000)flush(); *pp++=x;}void write(int x){ static int sta[20],top; if(!x){push('0');return;} while(x)sta[++top]=x%10,x/=10; while(top)push(sta[top--]^'0');}int main(){// freopen("G.in","r",stdin);// freopen("G.out","w",stdout); n=rd();m=rd(); for(int i=1;i<=m;++i){ a[i]=rd(); int tmp=a[i]/n; for(int k=1;k<=tmp;++k) for(int j=1;j<=m;++j)ans[j].pb(i); a[i]%=n; } for(int i=1,now=0;i<=m;++i){ now+=a[i]; if(now>=n)now-=n; if(i!=m)b[i]=mk(now,i); } sort(b+1,b+m); b[m]=mk(n,m); b[0]=mk(0,0); for(int i=1;i<=m;++i)pos[b[i].se]=i; for(int i=1,lst=1,now=0;i<=m;++i){ now+=a[i]; if(now>=n){ for(;lst<=m;++lst)ans[lst].pb(i); lst=0;now-=n; } if(!now)continue; for(;lst<=pos[i];++lst)ans[lst].pb(i); } cnt=ans[1].size(); write(cnt),push('\n'); for(int i=1;i<=m;++i)write(b[i].fi-b[i-1].fi),push(' '); push('\n'); for(int i=0;i