The Parade

Created by LXC on Fri Jul 14 09:18:10 2023

https://codeforces.com/problemset/problem/1250/J

ranting: 1800

tag: binary search, greedy

problem

现有不同升高的士兵n种，分别为$c_1, c_2, \cdots, c_n$，升高为i的士兵有$c_i$个。

我们需要选择k排士兵，每排人数相同，且每排中任意两个士兵的升高差绝对值不超过1。

问最多能选择多少士兵。

solution

设f(x)为每排士兵的个数是x时，形成的排数能否大于k。f(x)如果能那么f(x-1)也能，显然f(x)是一个单调函数。

我们可以二分每排的士兵个数。

然后对于确定每排士兵个数为x时，采取贪心策略可以构造最大的排数。

对于$c_i$，我们首先能够构造$\lfloor \frac{c_i}{x} \rfloor$排，然后剩余的$c_i = c_i % x$，可以与后面的$c_{i+1}$组合形成一排。但前提是$c_i+c_{i+1} \ge x$，否则将跳过当前$c_i$，继续对$c_{i+1}$重复此过程。

为什么跳过$c_i$会正确？此时的$c_i < x$且$c_i+c_{i+1} < x$。$c_i$无法与后面结合形成一排，即便与前面的某些数形成了一排，仍然会多出$c_i < x$个，这无法形成一排，所以升高1到i的人里面形成的排数是不会改变的。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll& i : a)
        cin >> i;
    ll l = 1, r = 3e17;
    while (l < r) {
        ll m = (r - l) / 2 + l;
        ll cnt = 0;
        vector<ll> b = a;
        for (int i = 0; i < n; i++) {
            if (b[i] >= m) {
                cnt += b[i] / m;
                b[i] %= m;
            }
            if (i + 1 < n && b[i] + b[i + 1] >= m) {
                cnt++;
                b[i + 1] -= m - b[i];
                b[i] = 0;
            }
        }
        // cout << m << " " << cnt << endl;
        if (cnt >= k) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    cout << (r - 1) * k << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}