题目大意:
给定集合,对于任意一个的排列,记,求。
很明显每次搞出一个长度为的最长上升序列,然后把元素给删掉,答案增加。
直接暴力需要。
但是可以进行优化。
设有个,将个数从小到大排序,记为长度为的数组。
则答案为
于是可以优化到。
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int T=1001;
int n;
int a[T],len;
inline int read(void)
{
int x=0; char c=getchar();
for (;!isdigit(c);c=getchar());
for (;isdigit(c);c=getchar()) x=x*10+c-'0';
return x;
}
int main(void)
{
n=read();
for (int i=1;i<=n;i++) a[read()]++;
printf("%d\n",n-*max_element(a,a+T));
return 0;
}