蓝桥杯第十三届蓝桥杯大赛软件赛决赛C/C++ 研究生组之好等差数列

蓝桥杯第十三届蓝桥杯大赛软件赛决赛C/C++ 研究生组之好等差数列

[题目传送门](0好等差数列 - 蓝桥云课 (lanqiao.cn))

本题大意就不再详细赘述，使用的方法为暴力破解，但最后也可以完全通过。

基本思路为：

枚举公差d，根据题意可以猜测，公差的范围为0–10000/n，由于v最大为10000.

使用哈希表存储对应d条件下的值，根据等差数列的公式我们知道，ai=a1+i*d,现在可以反过来使用，即a1 = ai-i * d,当d为合适的值时，则a1出现的次数将为最多。

例如：1，2，3，5，4.这5个数字。

在公差为0时，1-1*0=1；其中1 * 0中的1为数列的下标。

2-1*0=2;…

在公差为1时，1-1*1=0；2-1 * 2=0；3-1 * 3=0；5-1 * 4=1；4-1 * 5 =-1；

可以看到此时0出现了3次，1和-1均出现1次。则其离好数列的距离为n-3 = 5 -3=2,即将5和4这两个值更改即可。

代码如下所示：

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  vector<int> nums(n,0);
  unordered_map<int,int> co_nums;
  for(int i=0;i<n;i++)
  {
      cin>>nums[i];
  }
  int m;
  cin>>m;
  while(m--)
  {
      int p,v;
      cin>>p>>v;
      nums[p]=v;
      int ans=0;
      for(int d=0;d<=10000/n;d++)
      {
        for(int i=0;i<n;i++)
        {
          int temp = nums[i]-(i+1)*d;
          co_nums[temp]++;
          //cout<<co_nums[temp]<<endl;
          ans = max(ans,co_nums[temp]); //取其中出现次数最多的值
          //cout<<ans<<endl;
        }
        co_nums.clear(); //将哈希表清零
      }
      cout<<n-ans<<" ";
  }
  return 0;
}