C. Paprika and Permutation

原题链接

题目大意

输入：长度为n的数组

操作：任选一个 \(a_i\) 和 $x > 0 $，令 \(a_i\ =\ a_i\ mod\ x\)

目标：将数组变为从1到n的全排列

输出：操作的最少次数，若无法操作，则输出 -1

时间：\(O(n)\)

这是一道简单的找规律贪心题，但在某个地方的逻辑写复杂了，导致写错了……

所以以后写题的时候尽量想多一点，尽量用简单的写法，降低代码复杂度

另外，还是不过的话可以自己多造样例找问题

• 找规律

  • 通过操作将 a 变成 b，必须满足 a > 2 * b
  • 所以将多出的数和缺少的数从小到大映射就好

• 卡点

  • 找出需要变的数时逻辑太复杂，导致写错
  • 简化逻辑：使用set 判断需要改变的数

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int num[N];

int main()
{
    int time;
    cin >> time;

    while(time--)
    {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) cin >> num[i];
        sort(num, num + n);
        bool flag = true;
        vector<int> v1, v2;
        unordered_set<int> ss;
        // 简化逻辑
        for(int i = 0; i < n; i++)
        {
            if(num[i] >= 1 && num[i] <= n && !ss.count(num[i])) 
                ss.insert(num[i]);
            else v1.push_back(num[i]);	// 记录需要改变的数
        }
        // 遍历集合，找出缺少的数
        for(int i = 1; i <= n; i++)
            if(!ss.count(i)) v2.push_back(i);

        if(v1.size() != v2.size()) flag = false;
        if(flag)
        {
            for(int i = 0; i < v1.size(); i++)
            {
                if(v1[i] <= v2[i] * 2)
                {
                    flag = false;
                    break;
                }
            }           
        }
        if(!flag)
        {
            cout << "-1" << endl;
        }
        else cout << v1.size() << endl;
    }
    
}