251021cch模拟赛总结

wendywu · 2025-10-21 14:17:37 · 个人记录

100 + 100 + 100 + 30 = 330

然后想到b一定是反复的用同一个，所以考虑枚举这个b，那么a就只会贪心的选比这个b大的，和这个b对应的a

然后大样例就WA了，应为n会比m小，就把ans初始化一下，然后枚举b的时候如果要选的a比n多就跳过

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

using namespace std;

const int N = 3e5 + 5;

LL t, n, m, aa[N], s[N];
struct zs {
  LL a, b;
} a[N];

bool cmp (zs x, zs y) {
  return x.b > y.b;
}

int main () {
  // freopen("shop.in", "r", stdin);
  // freopen("shop.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> t; t--;) {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
      cin >> a[i].a >> a[i].b;
      aa[i] = a[i].a;
    }
    sort(a + 1, a + n + 1, cmp);
    sort(aa + 1, aa + n + 1);
    s[n + 1] = 0;
    for (int i = n; i >= 1; i--) {
      s[i] = s[i + 1] + aa[i];
    }
    LL ans = s[max(0ll, n - m + 1)];
    for (int i = 1; i <= n; i++) {
      LL k = lower_bound(aa + 1, aa + n + 1, a[i].b) - aa;
      if (k <= n - m + 1) continue;
      ans = max(ans, s[k] + (a[i].a >= a[i].b ? a[i].b * (m - (n - k + 1)) : a[i].a + a[i].b * (m - (n - k + 2))));
    }
    cout << ans << '\n';
  }
  return 0;
}

C - divide

卡掉人类智慧！！！卡掉人类智慧！！！卡掉人类智慧！！！卡掉人类智慧！！！卡掉人类智慧！！！卡掉人类智慧！！！

卡掉人类祝睿

看完题第一反应是dp，设f[i]表示1-i的答案

转移：f[i] = max_{j = 0}^{i - 1}{f[j] + v(j + 1, i)}