CF1305H Kuroni the Private Tutor

· · 题解

提供一个简单一点的方法。

先不管目标要求什么，列出题目所给出的限制。

设第 i 道题目最终有 a_i 人答对，第 i 名分数为 s_i，那么 l_i,r_i 的限制可以结合 hall 定理，贪心的按分数从大到小考虑人集合，那么应该有：

\sum_{i=1}^n \min(a_i,k) \ge \sum_{i=1}^k s_i

总分限制：

\sum_{i=1}^n a_i = t

对于每一题：

l_i \le a_i \le r_i

不同人之间：

s_i \ge s_{i+1}

最终所求的目标与最高分有关。

这样看来 l_i,r_i 与实际目标的关系非常微弱，它们只是通过限制 a_i 从而达到间接限制 s_i 的目的，此处就可以贪心的构造 a 数组了（a 较为均匀的偏小更优）。

考虑如何构造。先将每个 a_i 赋为最初始的 l_i，之后是让这些 a_i 尽量的平均，每一次选出未达到 r_i 中最小的 a_i 增加 1 即可。直接这样显然到 O(t \log n) 了，那么每一次让最小值合并到次小值当中，一个数达到上届 r_i 时扔出去就行了。

整理一下转换之后的问题，给出了限制

\sum_{i=1}^k s_i \le S_i,\sum_{i=1}^n s_i = t s_i \ge s_{i+1}

以及固定一些排名的人的分数。

使得并列第一人数最多，和在人数最多前提下第一名分数最高。

先用固定分数加强 S 的限制，即 S_i = \min(S_i, S_{i+1} - c_{i+1})，其中 c_i 表示排名为 i 的人的最小分数。

首先并列第一的人数是有单调性的，可以二分。剩下是一个判断问题。设并列第一人数至少为 x。这里第一名的分数可以直接满足 S_i(i \le x) 条件最大的。最后挨着扫一遍，当扫到一个数时，贪心的尽量填最大的即可，这样更容易满足总分的限制。

时间复杂度 O(n \log n)。具体细节可以看代码。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define inf (ll)1e18
#define pii pair <ll, ll>
#define fr first
#define se second
const ll mod = 1e9 + 7;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 18, stdin), p1 == p2) ? EOF : *p1++)
inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') f =((ch == '-') ? -1 : f), ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
inline void write(ll x) {
    if(x < 0) x = -x, putchar('-');
    if(x >= 10) write(x / 10);
    putchar(x % 10 + '0');
}
inline void Wro() {
    printf("-1 -1\n");
    exit(0);
}
ll n, m, all, Q;
struct Pro {
    ll l, r;
}a[100005]; 
ll val[100005];
struct Stu {
    ll x, y;
}b[100005];
inline void initval() {
    priority_queue <pii, vector <pii>, greater <pii> > Qu;
    sort(a + 1, a + 1 + n, [&] (Pro A, Pro B) {return A.l < B.l;});
    ll lst = all, upp = all;
    for(ll i = 1; i <= n; i++) lst -= a[i].l, upp -= a[i].r, val[i] = a[i].l;
    if(lst < 0 || upp > 0) Wro();
    a[n+1].l = inf;
    ll cnt = 0;
    for(ll i = 1; i <= n + 1; i++) {
        if(cnt) {
            ll tar = min(a[i].l - a[i-1].l, lst / cnt) + a[i-1].l;
            while(!Qu.empty()) {
                pii x = Qu.top();
                if(x.fr <= tar) {
                    lst -= (x.fr - a[i-1].l), val[x.se] = x.fr, cnt--;
                    if(cnt) tar = min(a[i].l - a[i-1].l, lst / cnt) + a[i-1].l;
                    Qu.pop();
                }
                else break;
            }
            if(tar == a[i].l) lst -= (tar - a[i-1].l) * cnt;
            else {
                lst -= (tar - a[i-1].l) * cnt;
                while(lst--) val[Qu.top().se] = tar + 1, Qu.pop();
                while(!Qu.empty()) val[Qu.top().se] = tar, Qu.pop();
                break;
            }
        }
        if(i == n + 1) break;
        Qu.push(mp(a[i].r, i)), cnt++;
    }
    for(ll i = 1; i <= n; i++) if(val[i] > m) Wro();
}
ll s1[100005], s2[100005], S[100005];
ll c[100005], d[100005];
inline void initS() {
    for(ll i = 1; i <= n; i++) s1[val[i]]++, s2[val[i]] += val[i];
    for(ll i = 1; i <= m; i++) s1[i] += s1[i-1], s2[i] += s2[i-1];
    for(ll i = 1; i <= m; i++) S[i] = s2[i] + (n - s1[i]) * i;
    for(ll i = m; i >= 1; i--) c[i] = max(c[i], c[i+1]);
    for(ll i = m - 1; i >= 1; i--) S[i] = min(S[i], S[i+1] - c[i+1]);
    memset(d, -1, sizeof d);
    for(ll i = 1; i <= Q; i++) d[b[i].x] = b[i].y;
}
ll num, mx, basmx;
inline bool chknum(ll mid) {
    ll kk = -1;
    for(ll i = 1; i <= mid; i++) {
        if(d[i] != -1) {
            if(kk == -1) kk = d[i];
            if(d[i] != kk) return 0;
        }
    }
    ll ans = n;
    for(ll i = 1; i <= mid; i++) ans = min(ans, (ll)floor(1.0 * S[i] / i));
    if(kk > ans) return 0;
    if(kk != -1) ans = kk;
    ll nowsum = ans * mid, lstmx = ans;
    for(ll i = mid + 1; i <= m; i++) {
        ll nowmx = min(all - nowsum, min(lstmx, S[i] - nowsum));
        if(nowmx < d[i] || nowmx < 0) return 0;
        if(d[i] != -1) nowsum += d[i], lstmx = d[i];
        else nowsum += nowmx, lstmx = nowmx;
    }
    if(nowsum != all) return 0;
    mx = ans;
    return 1;
}
inline void solvenum() {
    ll l = 1, r = m;
    while(l <= r) {
        ll mid = (l + r) / 2;
        if(chknum(mid)) l = mid + 1, num = mid;
        else r = mid - 1;
    }
}
int main() {
//  freopen("1.in", "r", stdin);
//  freopen("mine.out", "w", stdout);
    n = read(), m = read();
    for(ll i = 1; i <= n; i++) a[i].l = read(), a[i].r = read();
    Q = read();
    for(ll i = 1; i <= Q; i++) b[i].x = read(), b[i].y = read(), c[b[i].x] = b[i].y, basmx = max(basmx, b[i].y);
    sort(b + 1, b + 1 + Q, [&] (Stu A, Stu B) {return A.x < B.x;});
    for(ll i = 2; i <= Q; i++) if(b[i].x == b[i-1].x && b[i].y != b[i-1].y) Wro();
    all = read();
    initval(), initS(); 
    solvenum();
    if(num <= 0) Wro();
    write(num), putchar(' '), write(mx), putchar('\n');
    return 0;
}
/*
*/