題目鏈接

題意

長度為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; }

總結

以上是生活随笔為你收集整理的牛客IOI周赛19-普及组 B.小y的序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。