logoChat01.ai

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

創建於：2026年8月10日

使用 GPT-5.6 Thinking 回答 Chat01

問題

#include <bits/stdc++.h>
#define int long long
using namespace std;

using i128 = __int128;
using ld = long double;
const int INF = 1e15;
const int N = 1e3 + 7;
const int MOD = 1e9 + 7;

void solve() {
int n;
cin >> n;
vector< int > a(n + 2);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
a[0] = 0; a[n + 1] = 1001;
int x = a[0], dp = 0, ans = 0;
for (int i = 1; i <= n + 1; i++) {
if (a[i] - 1 == a[i - 1]) {
dp++;
ans = max(ans, dp - 1);
} else {
dp = 0;
}
}

cout << ans;
}

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int tests = 1;
//cin >> tests;
while (tests--) {
solve();
}

return 0;
}
вот мой слить написания полностью скопируй его и шаблон тож те менять ток в solve

У Вас есть игрушечное здание состоящее из n
башен. Каждая башня является столбиком кубиков, стоящих друг на друге. i
-я башня состоит из hi
кубиков и, соответственно, имеет высоту hi
.

Объявим операцию срезания по некоторой высоте H
следующим образом: для каждой башни i
, если её текущая высота больше H
, то уберем несколько верхних кубиков так, чтобы высота башни стала равна H
. Стоимость одного «срезания» равна суммарному количеству убранных кубиков со всех башен.

Назовем срез хорошим, если его стоимость меньше или равна k
(k≥n
).

Определите минимально возможное количество хороших срезов, необходимых для того, чтобы сделать все башни равными по высоте. Очевидно, что всегда существует способ выровнять башни.

Входные данные
Первая строка содержит два целых числа n
и k
(1≤n≤2⋅105
, n≤k≤109
) — количество башен и ограничение на срезы.

Вторая строка содержит n
целых чисел h1,h2,…,hn
(1≤hi≤2⋅105
) — первоначальные высоты башен.

Выходные данные
Выведите единственное число — минимально возможное количество хороших срезов, необходимых для того, чтобы сделать все башни равными по высоте.

Примеры
Входные данныеСкопировать
5 5
3 1 2 2 4
Выходные данныеСкопировать
2
Входные данныеСкопировать
4 5
2 3 4 5
Выходные данныеСкопировать
2
Примечание
В первом примере выгодно сделать 2
операции срезания. Первый срез по высоте 2
(его стоимость равна 3
) и второй по высоте 1
(его стоимость равна 4
).

задача идея решения это
разница в высотах всего n те считать сжать все дейстсвия между разницай в высоте напиши в моём стиле класный жадник

思考

Refining the batching logic

I’m handling each positive height gap without mutating the input. I’m filling the current operation, closing it when the next level no longer fits, then counting complete batches and retaining any final partial batch.

Worked for 51s

思考

Refining the batching logic

I’m handling each positive height gap without mutating the input. I’m filling the current operation, closing it when the next level no longer fits, then counting complete batches and retaining any final partial batch.

Worked for 51s

回答

Вот в твоём шаблоне — поменял только solve(). Сортируем высоты и идём сверху вниз: cnt — сколько башен сейчас режется одновременно, dif — сколько одинаковых по стоимости уровней между соседними высотами.

cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

using i128 = __int128;
using ld = long double;
const int INF = 1e15;
const int N = 1e3 + 7;
const int MOD = 1e9 + 7;

void solve() {
  int n, k;
  cin >> n >> k;
  vector< int > a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  sort(a.begin(), a.end());

  int dp = 0, ans = 0;

  for (int i = n - 1; i > 0; i--) {
    int cnt = n - i;
    int dif = a[i] - a[i - 1];

    if (dif == 0) continue;

    int can = (k - dp) / cnt;

    if (can >= dif) {
      dp += dif * cnt;
    } else {
      dif -= can;
      dp += can * cnt;

      if (dp) {
        ans++;
        dp = 0;
      }

      int can2 = k / cnt;

      ans += dif / can2;
      dif %= can2;

      dp = dif * cnt;
    }
  }

  if (dp) ans++;

  cout << ans;
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  srand(time(0));
  int tests = 1;
  //cin >> tests;
  while (tests--) {
    solve();
  }

  return 0;
}

Идея жадника: между двумя соседними различными высотами a[i] и a[i-1] есть dif уровней, и каждый такой уровень стоит cnt кубиков. В текущий срез максимально запихиваем (k - dp) / cnt таких уровней. Если весь промежуток не помещается — закрываем срез, а оставшуюся разницу сразу сжимаем через k / cnt, не перебирая каждый уровень.

Сложность: O(n log n) из-за сортировки, сам проход — O(n).

分享這個問答