251028cch模拟赛总结

wendywu · 2025-10-28 15:10:14 · 个人记录

100 + 100 + 20 + 100 = 320
md差点就能AK了qwq
T3居然是人类智慧，我写了一个双log结果T了
我再也不用map了，用了我是sb

T4第一次测的时候只有40pts：）事实证明，cch所有的spj都会炸：）

A - queue

首先想到暴力做法：
枚举V，然后枚举首项，然后算有几个不同

然后优化一下：先假设首项是0，然后算出每个人要变多少才能到他应该的身高。然后找到出现最多的这个变化量，把首项变成这个。

然后我们突然发现，这样复杂度其实是对的：）

因为V的个数只有\frac{w}{n}，然后其他的是O(n)的，所以复杂度就是：O(\frac{wn}{n}) = O(w)

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 3e5 + 5;

int n, w, a[N], c[N * 2], ans;

int main () {
  // freopen("queue.in", "r", stdin);
  // freopen("queue.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> w;
  ans = n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i * (n - 1) <= w; i++) {
    int mx = 0;
    for (int j = 1; j <= n; j++) {
      c[a[j] - j * i + w]++;
      if (a[j] - j * i + i < 1 || a[j] - j * i + i * n > w) continue;
      mx = max(mx, c[a[j] - j * i + w]);
    }
    ans = min(ans, n - mx);
    for (int j = 1; j <= n; j++) {
      c[a[j] - j * i + w]--;
    }
  }
  cout << ans;
  return 0;
}

B - compare