专栏文章

P13172题解

aallenchoi
P13172题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio5lkib
此快照首次捕获于
2025/12/02 13:44
3 个月前
此快照最后确认于
2025/12/02 13:44
3 个月前
查看原文
byd
afo 一个月，绿题弄了两三个晚上，笑拉了

题意：

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

Sol：

如果只考虑限制一，将座位从小到大扫，如果坐不下就加车次；
如果只考虑限制二，答案直接就是 max⁡cnti\max cnt_i，其中 cnticnt_i 表示第 ii 个人买票的数。
现在给出一个结论，如果我们先令 ans=max⁡cntians=\max cnt_i，之后我们就可以只考虑限制一了。证明如下：
假设 n=cn=c，且 cnticnt_i 都一样，且每个座位上恰好对应 cnticnt_i 张票。这种限制应该使最严格的。
按照上面的结论，ans=cntians=cnt_i。那对于每一趟车，我们就要在每个座位上选出对应的一张票，且这些票所属的人互不相同就行了。
考虑用二分图匹配证明。将座位（左）和人的编号（右）连边，那么我们每一轮都要找出完美匹配。可以用 Hall 定理。假设还剩 xx 趟车，那么一个大小为 aa 的左部点集，连出的边有 axax 条。由于这些边中，每个右部点最多连 xx 条边，所以 axax 条边涉及至少对应 aa 个右部点。因此，右部点集大于左部点集，根据 Hall 定理，必然存在完美匹配。
然后考虑计算答案。 设 sis_i 为座位 ii 对应的票数。
先将 ans1ans_1 设为 max⁡cnti\max cnt_i，那么之后可以把每个票看成除位置以外一样的。那么我们再将 ans1ans_1 和 max⁡1≤i≤n⌈∑1≤j≤isji⌉\max\limits_{1\le i\le n} \left\lceil\frac{\sum\limits_{1\le j\le i} s_j}{i}\right\rceil 取最大即可（因为相当于从左到右扫座位，每一次把多出来的人匀出去）。
那么 ans2ans_2 怎么算呢？根据上面的结论，对于每个 ii，如果 si>ans1s_i>ans_1，则 ans2ans_2 加上 si−ans1s_i-ans_1。

Code：

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...