专栏文章

Not Too Many Balls-ABC332G

AArrtan_73
AT_abc332_g题解参与者 2已保存评论 3

文章操作

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

当前评论
3 条
当前快照
1 份
快照标识符
@miobke43
此快照首次捕获于
2025/12/02 16:31
3 个月前
此快照最后确认于
2025/12/02 16:31
3 个月前
查看原文

题目大意

给定 nn 种球和 mm 个盒子，对于第 ii 种球有 aia_i 个，第 ii 个盒子的容量为 bib_i，且对于所有满足 1≤i≤n1 \le i \le n 且 1≤j≤m1 \le j \le m 的整数对 (i,j)(i, j)，第 jj 个球盒子最多放 i×ji \times j 个第 ii 种球，求最大的放置数。
1≤n≤500,1≤m≤1051 \le n \le 500, 1 \le m \le 10^5。

Sol

不难想到网络流算法。
建立源汇点，对于每种球和每一个盒子都新建一个点，源点向球连边，流量为 aia_i，盒子向汇点连边，流量为 bib_i，球向盒子连边，流量为 i×ji \times j，答案即为最大流。
在此数据范围下，网络流复杂度会炸，由于这个图的结构特殊性，考虑用 dpdp 模拟网络流。
先将最大流转为最小割，则我们所求即为：
min⁡(∑i∈Xai+∑j∈Ybj+∑i∉X∑j∉Yij)\min (\sum_{i \in X}a_i + \sum_{j \in Y}b_j+\sum_{i \notin X}\sum_{j \notin Y}ij)
我们设 ∑i∉Xi=k\sum_{i \notin X}i = k，则对于所有满足 ∑i∉Xi=k\sum_{i \notin X}i = k 的集合 XX 求出最小的 ∑i∈Xai\sum_{i \in X}a_i，显然背包解决即可，则原式化为：
dpk+k∑j∉Yj+∑j∈Ybjdp_k + k\sum_{j \notin Y}j + \sum_{j \in Y}b_j
对于每一个可能的 kk，贪心地取 min⁡(bj,jk)\min(b_j, jk)，不难发现将 bb 按照 ⌊bjj⌋\lfloor{b_j \over j}\rfloor 排序，则取 bjb_j 和取 jkjk 的部分为一段前缀和一段后缀，在枚举 kk 的过程中同时维护两部分的分界点即可。
由于在递增枚举 kk 的过程中，分界点也是单调递增的，最多移动 mm 次，保证了复杂度的正确性。
时间复杂度 O(n3+m)O(n ^ 3 + m)。

Code

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e2 + 5, M = 5e5 + 5;
int a[N], b[M], dp[N * N], n, m, Ans = 1e18, pos[M];
bool compare(int i, int j){return (int)(b[i] / i) < (int)(b[j] / j);}
signed main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++)cin >> a[i];
	for(int i = 1; i <= m; i++)cin >> b[i];
	memset(dp, 0x3f, sizeof dp);
	dp[0] = 0;
	for(int i = 1; i <= n; i++)
		for(int k = n * (n + 1) / 2; k >= i; k--)
			dp[k] = min(dp[k], dp[k - i] + a[i]);//01背包
	for(int i = 1; i <= m; i++)pos[i] = i;
	sort(pos + 1, pos + m + 1, compare);//按照b[j] / j升序排序
	int sum1 = m * (m + 1) / 2, sum2 = 0, loc = 1;
	for(int i = 0; i <= n * (n + 1) / 2; i++){
		while(i * pos[loc] > b[pos[loc]]){//维护分界点
			sum1 -= pos[loc];
			sum2 += b[pos[loc]];
			loc++;
		}
		Ans = min(Ans, dp[n * (n + 1) / 2 - i] + i * sum1 + sum2);//维护答案
	}
	cout << Ans << endl;
	return 0;
}

评论

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

正在加载评论...