【BZOJ2587】【CEOI2011】Teams

Author Avatar
q234rty 9月 23, 2017

动态规划+堆即可。

将 a_i 从大到小排序，容易发现每一个团队都是一个区间。

考虑暴力DP：设 f(i) 为前 i 个人最多分成的团队个数， g(i) 为前 i 个人分成 f(i) 个团队，最大的团队的最少成员数。

易得

f(i)=\max_{j+a_{j+1}\leq i} f(j)+1\\ g(i)=\min_{j+a_{j+1}\leq i,f(j)+1=f(i)} \max(g(j),i-j)

考虑用一个链表维护 i 处新增的决策点，计算好 j 后把其添加到 a_{j+1}+j 处的链表中。

注意到 g(j) 相对 i 为常数，而 i−j 单调递增，那么一个 j 随 i 的增加， \max(g(j),i-j) 应该先取 g(j) 再取 i-j 。

考虑再使用一个链表维护 i 处有哪些 j 满足 g(j)=i-j ，计算好 j 后把其添加到 g(j)+j 处的链表中。

对于 g(j)<i-j ，用一个堆维护 f(j) 的最大值及 f(j) 取最大时 g(j) 的最小值。

对于 g(j) \geq i-j ，直接记录 f(j) 的最大值及 f(j) 取最大时 j 的最大值即可。

时间复杂度 O(n \log n) 。

本题存在时间复杂度 O(n) 的做法，参见lych_cys的题解 。

Code

  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/priority_queue.hpp>
  3. using namespace std;
  4. typedef long long ll;
  5. const int MAXSIZE=30000020;
  6. const int INF=0x3f3f3f3f;
  7. int bufpos;
  8. char buf[MAXSIZE];
  9. #define NEG 0
  10. void init(){
  11.     #ifdef LOCAL
  12.         freopen("2587.txt","r",stdin);
  13.     #endif
  14.     buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  15.     bufpos=0;
  16. }
  17. #if NEG
  18. int readint(){
  19.     bool isneg;
  20.     int val=0;
  21.     for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  22.     bufpos+=(isneg=buf[bufpos]=='-');
  23.     for(;isdigit(buf[bufpos]);bufpos++)
  24.         val=val*10+buf[bufpos]-'0';
  25.     return isneg?-val:val;
  26. }
  27. #else
  28. int readint(){
  29.     int val=0;
  30.     for(;!isdigit(buf[bufpos]);bufpos++);
  31.     for(;isdigit(buf[bufpos]);bufpos++)
  32.         val=val*10+buf[bufpos]-'0';
  33.     return val;
  34. }
  35. #endif
  36. char readchar(){
  37.     for(;isspace(buf[bufpos]);bufpos++);
  38.     return buf[bufpos++];
  39. }
  40. int readstr(char* s){
  41.     int cur=0;
  42.     for(;isspace(buf[bufpos]);bufpos++);
  43.     for(;!isspace(buf[bufpos]);bufpos++)
  44.         s[cur++]=buf[bufpos];
  45.     s[cur]='\0';
  46.     return cur;
  47. }
  48. int cnt[1000002],tmp[1000002],a[1000002],b[1000002],f[1000002],g[1000002],lst[1000002];
  49. int nxt[1000002],first[1000002],nxt2[1000002],first2[1000002];
  50. void add(int p,int v){
  51.     nxt[v]=first[p];
  52.     first[p]=v;
  53. }
  54. void add2(int p,int v){
  55.     nxt2[v]=first2[p];
  56.     first2[p]=v;
  57. }
  58. struct cmp{
  59.     bool operator ()(const int &x,const int &y){
  60.         return f[x]<f[y] || (f[x]==f[y] && g[x]>g[y]);
  61.     }
  62. };
  63. typedef __gnu_pbds::priority_queue<int,cmp> heap;
  64. heap q;
  65. heap::point_iterator it[1000001];  
  66. int main(){
  67.     init();
  68.     int n=readint();
  69.     for(int i=1;i<=n;i++)
  70.         tmp[i]=readint(),cnt[tmp[i]]++;
  71.     for(int i=n;i;i--)
  72.         cnt[i]+=cnt[i+1];
  73.     for(int i=1;i<=n;i++)
  74.         b[cnt[tmp[i]]]=i,a[cnt[tmp[i]]--]=tmp[i];
  75.     int now=0;
  76.     //for(int i=1;i<=n;i++)
  77.         //printf("%d ",a[i]);
  78.     for(int i=1;i<=n;i++){ //g[j]+j<=i
  79.         //puts("WTF");
  80.         for(int to=first2[i];to;to=nxt2[to]){
  81.             if (g[to]+to<i){
  82.                 if (f[to]>=f[now])
  83.                     now=to;
  84.             }else {
  85.                 //printf("adding %d\n",to);
  86.                 it[to]=q.push(to);
  87.             }
  88.         }
  89.         //puts("233");
  90.         for(int j=first[i];j;j=nxt[j]){
  91.             if (j+a[j+1]>i)
  92.                 continue;
  93.             //printf("%d\n",j);
  94.             q.erase(it[j]);
  95.             if (f[j]>f[now] || (f[j]==f[now] && j>now))
  96.                 now=j;
  97.         }
  98.         //puts("tat");
  99.         if (q.empty()){
  100.             if (!now && i<a[1]){
  101.                 g[i]=INF;
  102.                 continue;
  103.             }
  104.             f[i]=f[now]+1;
  105.             g[i]=i-now;
  106.             lst[i]=now;
  107.         }else{
  108.             int x=q.top();
  109.             if (f[x]==f[now]){
  110.                 f[i]=f[x]+1;
  111.                 if (i-now<g[x])
  112.                     g[i]=i-now,lst[i]=now;
  113.                 else g[i]=g[x],lst[i]=x;
  114.             }else if (f[x]<f[now])
  115.                 f[i]=f[now]+1,g[i]=i-now,lst[i]=now;
  116.             else f[i]=f[x]+1,g[i]=g[x],lst[i]=x;
  117.         }
  118.         //puts("qwq");
  119.         //printf("f[%d]=%d\n",i,f[i]);
  120.         if (g[i]+i<=n)
  121.             add(g[i]+i,i);
  122.         if (i<n && i+a[i+1]<=n)
  123.             add2(i+a[i+1],i);
  124.     }
  125.     printf("%d\n",f[n]);
  126.     for(int i=n;i;){
  127.         int w=lst[i];
  128.         printf("%d ",i-w);
  129.         while(i>w){
  130.             printf("%d ",b[i]);
  131.             i--;
  132.         }
  133.         putchar('\n');
  134.     }
  135. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2017/09/23/bzoj2587/

隐藏