[CF743E]Vladik and cards

题目

传送门 to luogu

思路

一开始以为必须按照顺序来，也就是单调递增。然后看到样例二的时候震惊。

由于出现次数相差最多 $1$ ，那么值域肯定在 $[t,t+1]$ 内。这里的 $t$ 当然可以枚举啦！

仔细想想，如果出现 $t+1$ 次可以，那出现 $t$ 次也可以。那么这里的 $t$ 还是 二分 好啦！

找到了值域 $[t,t+1]$ ，再 $2^8$ 枚举谁出现了 $t+1$ 次就行啦！

现在我们怎么检查呢？这篇题解给出了朴素的想法，枚举其排列。常见套路：枚举排列改成状压！

$f(S)$ 表示， $S$ 中的元素都被搞定了，最少要用前多少个数字。这里是贪心的思路，因为选择的时候越靠前，后面的可操作性就越大。转移就枚举一个数字，用二分查找转移。

总复杂度 $\mathcal{O}(2^8\times 2^8\times 8?\log ?n)$ 。这篇题解中有别的方法，复杂度是 $\mathcal O(2^8\times 8\cdot n\log n)$ 。

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
inline int readint(){int a = 0; char c = getchar(), f = 1;for(; c<'0'||c>'9'; c=getchar())if(c == '-') f = -f;for(; '0'<=c&&c<='9'; c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}
template < class T >
void getMax(T&a,const T&b){if(a<b)a=b;}
template < class T >
void getMin(T&a,const T&b){if(b<a)a=b;}const int MaxN = 1000, MaxA = 8;
int cnt[MaxA+1][MaxN+1], n;int want[MaxA+1], dp[1<<MaxA];
bool check(){for(int S=1; S<(1<<MaxA); ++S){dp[S] = n+1;for(int i=0; i<MaxA; ++i)if(S>>i&1){ // 考虑最后一个int now = dp[S^(1<<i)];now = lower_bound(cnt[i+1]+now,cnt[i+1]+n+1,cnt[i+1][now]+want[i+1])-cnt[i+1];getMin(dp[S],now);}}return dp[(1<<8)-1] <= n;
}int main(){n = readint();for(int i=1; i<=n; ++i){for(int j=1; j<=MaxA; ++j)cnt[j][i] = cnt[j][i-1];++ cnt[readint()][i];}int L = 0, R = n/MaxA;while(L != R){for(int i=1; i<=MaxA; ++i)want[i] = (L+R+1)>>1;if(check()) L = (L+R+1)>>1;else R = (L+R+1)/2-1;}int ans = 8*L;for(int S=1; S<(1<<8); ++S){int newAns = 0;for(int i=0; i<MaxA; ++i){want[i+1] = (S>>i&1)+L;newAns += want[i+1];}if(check()) getMax(ans,newAns);}printf("%d\n",ans);return 0;
}