Codeforces - 1617C Paprika and Permutation

题意：给出一串数，每个操作可以选择一个数a和一个任意的模数x，将a换成a%x。问至少几次操作后可以将所有的数变成1-n的排列。

解：首先已经在1-n范围内的数不用动，考虑如何将其他数变成剩下的数，这显然要找个结论。由于多次取模和取一次可以有一样的结果，所以取一次就行了。

• 让a对任意数取模，得到的结果范围为[0,a/2)。
• 如果要把a变成b，那a%(a-b)显然是最可行的方案。如果a大于(a-b)的两倍，那就无法得到b了。
• 对于每一个要得到的b，如果a>=2*(a-b)，显然a>=2*(a-(b+1))，即后续的b无法从a处转换，a这数没用了。但排列是从1-n一一对应的，这样一来就会空一个。

因此，从小到大将现有的数和目标检查，有一个不符合要求，输出-1即可。

代码：

#include
using namespace std;
#define ll long long
#define maxx 200005
#define eps 0.000001
#define inf 0x3fffffff
int n,m,k;
int vis[maxx]={0};
int a[maxx];
signed main(){
    int T;
    scanf("%d",&T);
    while(T--) {
        memset(vis,0,sizeof vis);
        memset(a,0,sizeof a);
        scanf("%d", &n);
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            int temp;
            scanf("%d", &temp);
            if (temp > 0 && temp <= n&&!vis[temp])
                vis[temp]++;
            else
                a[++cnt] = temp;
        }
        sort(a + 1, a + 1 + cnt);
        int cnt2 = 0, ans = 0;
        int flag = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[i])
                continue;
            int temp=a[++cnt2];
            if (temp>=(temp-i)*2) {
                flag = 1;
                break;
            } else
                ans++;
        }
        if (flag)
            printf("-1\n");
        else
            printf("%d\n", ans);
    }
    return 0;
}