洛谷P10184 [YDOI R1] whk 题解

题目链接：P10184 [YDOI R1] whk

题意：

小 Z 一共要卷 \(n\) 门科目，第 \(i\) 门科目他有且只有 \(a_i\) 道题。有无数天时间，每天小 Z 可以做无数道题。

如果小 Z 认为一天是有趣的，仅当他在这一天至少做了 \(t\) 门科目的题。

小 Z 想知道最多有多少天是有趣的。

输入格式：

第一行，\(2\) 个正整数 \(n,t\)。

接下来一行，有 \(n\) 个整数，分别 \(a_1,a_2,a_3,\dots,a_{n-1},a_n\)。

输出格式：

一个整数，输出小 Z 认为有趣的天数的最大值。

数据范围：

\(1\le t\le n\le5\times10^5\)，\(1\le a_i \le 10^6\)。

一开始想到的是贪心，即用堆维护最多的 \(t\) 种题，答案的增量为这 \(t\) 个中最小的那个。

不过这样的复杂度是 \(\mathcal{O}(nt\log n)\) 的，因为每次减去最小值最少只会去掉一个种类

实际上，我们只需要二分一下这个天数 \(x\) 就可以判断了，对于每个 \(a_i\) 它至多用 \(\max(a_i,x)\) 次

时间复杂度 \(\mathcal{O}(n \log nV)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))

int n, t, l, r, a[N];
bool check(int x)
{
    int sum = 0;
    for(int i = 1; i <= n; i++) sum += min(a[i], x);
    return sum >= x * t;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> t;
    for(int i = 1; i <= n; i++) cin >> a[i], r += a[i];
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        check(mid) ? l = mid : r = mid - 1;
    }
    cout << l << '\n';
    return 0;
}

---

题外话：

双倍经验：[ABC227D] Project Planning ，不过需要加一个 __int128_t