2020-2021:teams:legal_string:jxm2001:contest:arc_125
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:legal_string:jxm2001:contest:arc_125 [2021/08/23 17:10] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:arc_125 [2021/08/23 21:09] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 75: | 行 75: | ||
| </hidden> | </hidden> | ||
| + | ===== E - Snack ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $n$ 种物品，第 $i$ 种物品有 $a_i$ 个。给定 $m$ 个背包，第 $i$ 个背包大小为 $c_i$，且同种物品最多只能放 $b_i$ 个。 | ||
| + | |||
| + | 问 $m$ 个背包最多能装下的物品数。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 首先考虑网络流建图，将第 $i$ 个物品作为点 $L_i$，第 $j$ 个背包作为点 $R_j$。建边 $S\to L_i$，容量为 $a_i$。$L_i\to R_j$，容量为 $b_j$。$R_i\to T$，容量为 $c_i$。 | ||
| + | |||
| + | 于是答案为最大流，同时也等于最小割，考虑快速最小割计算。 | ||
| + | |||
| + | 假设已经确定保留 $k$ 条 $S\to L_i$ 的连边。那么对每个 $R_i$，显然他的割是 $\min(k\times b_i,c_i)$，且 $R_i,R_j$ 的选项互不影响。 | ||
| + | |||
| + | 于是可以将所有 $L_i$ 按 $a_i$ 排序，所有 $R_i$ 按 $\frac {c_i}{b_i}$ 排序。枚举 $k\in [0,n]$，用一个指针维护哪些 $R_i$ 贡献为 $k\times b_i$，哪些 $R_i$ 贡献为 $c_i$。 | ||
| + | |||
| + | 然后前缀和统计贡献，时间复杂度 $O\left(n\log n+m\log m\right)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=2e5+5; | ||
| + | const LL inf=1e18; | ||
| + | LL a[MAXN],preb[MAXN],prec[MAXN]; | ||
| + | struct Node{ | ||
| + | unsigned long long b,c; | ||
| + | bool operator < (const Node &t)const{ | ||
| + | return c*t.b>t.c*b; | ||
| + | } | ||
| + | }node[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | LL s=0,ans=inf; | ||
| + | _for(i,0,n) | ||
| + | a[i]=read_LL(); | ||
| + | sort(a,a+n); | ||
| + | _rep(i,1,m) | ||
| + | node[i].b=read_LL(); | ||
| + | _rep(i,1,m) | ||
| + | node[i].c=read_LL(); | ||
| + | sort(node+1,node+m+1); | ||
| + | _rep(i,1,m){ | ||
| + | preb[i]=preb[i-1]+node[i].b; | ||
| + | prec[i]=prec[i-1]+node[i].c; | ||
| + | } | ||
| + | int pos=1; | ||
| + | _rep(i,0,n){ | ||
| + | while(pos<=m&&node[pos].b*(n-i)<node[pos].c) | ||
| + | pos++; | ||
| + | ans=min(ans,s+preb[pos-1]*(n-i)+prec[m]-prec[pos-1]); | ||
| + | s+=a[i]; | ||
| + | } | ||
| + | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/arc_125.1629709821.txt.gz · 最后更改: 2021/08/23 17:10 由 jxm2001
