一种清晰直观的思路,却WA了部分,这是为什么
查看原帖
一种清晰直观的思路,却WA了部分,这是为什么
722677
iamputin楼主2023/9/29 11:25
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 10005;
const int inf = numeric_limits<int>::max();

#ifndef ONLINE_JUDGE
#include <oi_debug/debug.hpp>
#else
#define debug(x)
#endif // ONLINE_JUDGE

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T;
  cin >> T;
  while (T--) {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> c(n);
    for (int i = 0; i < n; ++i) {
      cin >> c[i];
    }
    int l = 0, r = l;
    priority_queue<int> pq;
    int ans = 0;
    while (l < n) {
      while (r < n && c[r] == c[l]) r++;
      if (r - l > 1)
        pq.push(r - l);
      ans++;
      l = r;
    }
    while (!pq.empty() && m > 0) {
      int elem = pq.top();
      pq.pop();
      if (elem == 1) break;
      if (elem == 2) ans += 1;
      else {
        if (elem & 1) {
          pq.push((elem - 1) / 2);
          pq.push((elem - 1) / 2);
        } else {
          pq.push(elem / 2);
          pq.push(elem / 2 - 1);
        }
        ans += 2;
      }
      m--;
    }
    cout << ans << endl;
  }
}

我是取块然后从大的开始切,每次取最大的切 这个思路有什么错误的吗,有没有大佬救救!

Orz

2023/9/29 11:25
加载中...