P13172题解

· · 题解

byd
afo 一个月，绿题弄了两三个晚上，笑拉了

题意：

有 n 个座位，c 个客户，他们共买了 m 张车票。每张票有两个属性 p_i,b_i，p_i 是座位编号，b_i 是客户编号。你可以做若干的操作，每次操作可以将一张票的 p_i 改小一些。要求一趟车中，一个座位只能坐一人，一个人在一趟车中只能占据一个座位。问通过这些操作，最少可以用多少趟车使所有票都用掉，该情况下最少用几次操作。

Sol：

如果只考虑限制一，将座位从小到大扫，如果坐不下就加车次；
如果只考虑限制二，答案直接就是 \max cnt_i，其中 cnt_i 表示第 i 个人买票的数。

现在给出一个结论，如果我们先令 ans=\max cnt_i，之后我们就可以只考虑限制一了。证明如下：
假设 n=c，且 cnt_i 都一样，且每个座位上恰好对应 cnt_i 张票。这种限制应该使最严格的。
按照上面的结论，ans=cnt_i。那对于每一趟车，我们就要在每个座位上选出对应的一张票，且这些票所属的人互不相同就行了。

考虑用二分图匹配证明。将座位（左）和人的编号（右）连边，那么我们每一轮都要找出完美匹配。可以用 Hall 定理。假设还剩 x 趟车，那么一个大小为 a 的左部点集，连出的边有 ax 条。由于这些边中，每个右部点最多连 x 条边，所以 ax 条边涉及至少对应 a 个右部点。因此，右部点集大于左部点集，根据 Hall 定理，必然存在完美匹配。

然后考虑计算答案。 设 s_i 为座位 i 对应的票数。
先将 ans_1 设为 \max cnt_i，那么之后可以把每个票看成除位置以外一样的。那么我们再将 ans_1 和 \max\limits_{1\le i\le n} \left\lceil\frac{\sum\limits_{1\le j\le i} s_j}{i}\right\rceil 取最大即可（因为相当于从左到右扫座位，每一次把多出来的人匀出去）。
那么 ans_2 怎么算呢？根据上面的结论，对于每个 i，如果 s_i>ans_1，则 ans_2 加上 s_i-ans_1。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int T,n,c,m,ans1,ans2,c1[N],c2[N];
int main()
{
    scanf("%d",&T);
    for(int t = 1;t <= T;t++)
    {
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        scanf("%d%d%d",&n,&c,&m);
        for(int i = 1,p,b;i <= m;i++) scanf("%d%d",&p,&b),c1[p]++,c2[b]++;
        ans1 = ans2 = 0;
        for(int i = 1;i <= c;i++) ans1 = max(ans1,c2[i]);
        for(int i = 1,s = 0;i <= n;i++) s += c1[i],ans1 = max(ans1,(s + i - 1) / i);
        for(int i = 1;i <= n;i++) if(c1[i] > ans1) ans2 += c1[i] - ans1;
        printf("Case #%d: %d %d\n",t,ans1,ans2);
    }
    return 0;
}