牛客IOI周赛19-普及组 B.小y的序列

题目链接

题意

长度为n的序列，最少需要修改多少个数字，满足$a[i+1]=a[i]+i,i\in [2,n]$。

思路1

满足等式的序列是固定的，可以用序列的首元素$a_0$表示整个序列，也就是说序列的首元素$a_0$，对应一个唯一的序列。 遍历整个数组，假设当前数字不需要调整，对这个序列进行计数，即通过计算得到首元素，对这个首元素进行标记。 最后选择一个出现次数最多的一个序列，它对应调整的数字最少。

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<long long> arr(n); for (long long &it : arr) cin >> it; map<long long, int> mp; int mx = 0; for (int i = 1; i <= n; ++i) { long long t = arr[i-1] - 1ll*(i-1)*i/2; mp[t]++; mx = max(mx, mp[t]); } cout << n - mx << endl; return 0; }

思路2

通过构造一个满足的序列，然后计算给定序列对应的偏移量，最后选择出现次数最多的偏移量，即对应最少的修改。

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<long long> arr(n); vector<int> tmp(n, 0); for (long long &it : arr) cin >> it; map<long long, int> mp; long long num = 0; int mx = 0; for (int i = 0; i < n; ++i) { num += i; long long t = arr[i] - num; mp[t]++; mx = max(mx, mp[t]); } cout << n - mx << endl; return 0; }