CF1790D Matryoshkas
题意
ZYH 的玩具有很多种类，每种玩具都是一段连续的区间（如 \([3,4,5]\) ）
ZYH 有很多种玩具，但是他不慎把所有玩具的元素乱序混合到了一起。例如玩具 \([1,2,3,4]\) 和玩具 \([2,3]\) 混合到一起后可能是 \([2,2,3,4,3,1]\)。
给定混合后的序列 \(a\)，SA 想知道 ZYH 最初最少有多少个玩具。
思路
其实这道题就是要从一个大序列中提取若干个连续子序列（顺序可交换）
那么，首先肯定将其排序。
接着，考虑用 \(f_i\) 表示有多少个末尾为 \(i-1\) 的子序列（即，接下来需要找 \(i\) 插入这个序列）
来手玩一下样例：
最初的 \(f\) 是这样的：
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| \(f_i\) |
首先插入 \(1\) ， \(1\) 前面并没有一个串（也就是 \(f_1=0\) ，所以直接更新 \(f_2\) 为 \(1\) 即可:
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| \(f_i\) | 1 |
这时插入\(2\)，此时\(f_2=1\)，那么说明这个\(2\)可以和以前的某个序列接上，那么现在\(f_2\)就是\(0\)，转而\(f_3\)是\(1\)：
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| \(f_i\) | 0 | 1 |
接着，又来个一个\(2\)，但是此时\(f_2\)已经为\(0\)，所以直接加在\(f_3\)：
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| \(f_i\) | 0 | 2 |
随后的两个\(3\)可以将\(f_3\)变为\(0\)，而将\(f_4\)变为\(2\)：
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| \(f_i\) | 0 | 0 | 2 |
最后一个数是\(4\)，发现\(f_4\)不为\(0\)，那就接在它后面并更新：
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| \(f_i\) | 0 | 0 | 1 | 1 |
所以最后的答案就是\(f\)中所有数之和
代码
#include<bits/stdc++.h>
using namespace std;
const int Maxn=2e5+10;
int n,ans;
int a[Maxn];
void run()
{
cin>>n;map<int,int>f;ans=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
if(f[a[i]]!=0) f[a[i]]--;
f[a[i]+1]++;
}
for(map<int,int>::iterator it=f.begin();it!=f.end();it++)
{
ans+=it->second;
}
cout<<ans<<endl;
}
int main()
{
int t;
cin>>t;
while(t--) run();
}