就c有点意思,A,B,D1感觉都很好想。
C - Paprika and Permutation
题意:
给定了一个数组,要求转换成一个排列,问能否变换,如果能,输出最小操作次数。
这里的操作是,选择整数x,然后a[i] %= x;
做法:
已经在1~n里的数可以不去动了,剩下的数,考虑怎么变成排列里的数。
这里一时想不到怎么去变,可以稍微打个表,然后就很容易发现,n可以通过一次操作,变成1~(n - 1) / 2的数。
然后这题就做完了,贪心的从小到大遍历,能变成排列里的数,那就变。
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
set<int> s, f;
for (int i = 1; i <= n; i++) s.insert(i), f.insert(i);
for (int i = 1; i <= n; i++) {
cin >> a[i];
s.erase(a[i]); //还缺的数
}
int cnt = 0;
sort(a.begin(), a.end());
for (int i = 1; i <= n; i++){
if (f.count(a[i])){
f.erase(a[i]); //要是不在这个排列里面,那就要开始变化了
continue;
}
int ans = 1e18;
for (auto j : s){
if ((a[i] - 1) / 2 < j) continue;
ans = j;
break;
}
s.erase(ans);
cnt++;
}
if (s.size()) cout << "-1\n";
else cout << cnt << "\n";
}