首页 > 其他分享 >ABC332G Not Too Many Balls 题解

ABC332G Not Too Many Balls 题解

时间:2023-12-15 19:23:18浏览次数:33  
标签:Balls int 题解 sum long leq Many ll define

第 \(i\) 种球有 \(a_i\) 个,共 \(n\) 种。

第 \(i\) 种箱子最多共装 \(b_i\) 个球。共 \(m\) 种。

第 \(i\) 种球在第 \(j\) 种箱子里至多放 \(ij\) 个。

问所有箱子放的球数最多是多少。

\(1\leq n\leq 500,1\leq m\leq 5e5,0\leq a_i,b_i\leq 1e12\)。

很容易建出网络流模型。从上至下依次有 \(1,n,m,1\) 个点。但是图实在太大了。

考虑求最小割。那就是要把上下共 \(n+m\) 个点划分为两类。

将它表示出来。设上下的全集分别为 \(X=\{1,2,...,n\},Y=\{1,2,...,m\}\)。

上下分别选了 \(P\subseteq X,Q\subseteq Y\) 归于源点集合。(以下所有式子所有求和条件略去这两个)

\[\sum_{i\in X/P}a_i+\sum_{i\in P}i\sum_{j\in Y/Q}j+\sum_{i\in Q}b_i \]

这个东西的最小值不好求。因为既要考虑 \(P\) 也要考虑 \(Q\)。

观察到数据范围很小,考虑枚举一点东西来把问题划分成独立的两个问题。枚举中间项左侧的 \(k=\sum_{i\in X}i\)。

有 \(0\leq k\leq n(n+1)/2\)。

那么对最左项的限制就是选一些求和为 \(k\) 的 \(i\),作为 \(P\)。剩下的 \(a_i\) 加起来作为这一项。

写在求和的条件上就是:

\[\sum_{i\in X/P,k=\sum_{i\in X/P} i}a_i+k\sum_{i\in Y/Q}i+\sum_{i\in Q}b_i \]

下面一行要么纳入源点集合,在第三项计算。否则在第二项计算。

发现此时下面一行对于是否纳入源点集合不受约束。贪心地让它取较小的,使得整个式子最小。

\[\sum_{i\in X/P,k=\sum_{i\in X/P} i}a_i+\sum_{1\leq i\leq m}\min(ik,b_i) \]

那么可以分别求出左侧和右侧对于每个 \(k\) 的最小值,相加。

左侧可以用 \(O(n^3)\) 的 DP 算出,右侧可以发挥智慧写出 \(O(n^2+m)\)。这部分比较简单。

总时间复杂度为 \(O(n^3+m)\)。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define rg register
#define ld long double
#define ull unsigned long long
#define gc getchar
#define pc putchar
#define pob pop_back
#define ump unordered_map
#define vi vector<int>
#define vl vector<ll>
#define fo(i,l,r) for(rg int i=(l);i<=(r);++i)
using namespace std;
inline int re() {
	rg int x=0,p=0;rg char c=getchar();
	while(c<'0'||c>'9') (!p)?(p=c=='-'):(p=p),c=getchar();
	while('0'<=c&&c<='9') (x*=10)+=c-48,c=getchar();
	if(p) x=-x;
	return x;
}
inline ll rel() {
	rg ll x=0;rg int p=0;rg char c=getchar();
	while(c<'0'||c>'9') (!p)?(p=c=='-'):(p=p),c=getchar();
	while('0'<=c&&c<='9') (x*=10)+=c-48,c=getchar();
	if(p) x=-x;
	return x;
}
inline void wt(rg int x) { if(x>9) wt(x/10);pc(x%10+48); }
inline void wtl(rg ll x) { if(x>9) wtl(x/10);pc(x%10+48); }

const int N=505;
const int M=5e5+5;
const ll inf=1e18;
int n,m;
ll a[N],b[M],f[N*(N+1)/2],ans=inf;
ll minl(ll a,ll b) { return a<b?a:b; }
struct pr { ll t;int i; }c[M];
bool cmp_by_t(pr a,pr b) { return a.t<b.t; }
int main() {
//	freopen(".in","r",stdin),freopen(".out","w",stdout);
	n=re(),m=re();
	fo(i,1,n) {
		a[i]=rel();
	}
	fo(i,1,m) {
		b[i]=rel();
	}
	vector<vl>f(n+1,vl(n*(n+1)/2+1,inf));
	int sum=0;
	f[0][0]=0;
	fo(i,0,n-1) {
		for(int j=sum;j>=0;j--) {
			f[i+1][j+i+1]=minl(f[i+1][j+i+1],f[i][j]);
			f[i+1][j]=minl(f[i+1][j],f[i][j]+a[i+1]);
		}
		sum+=i+1;
	}
	ll s1=0,s2=0,si=0;
	fo(i,1,m) {
		si+=i;
		c[i].t=b[i]/i;
		c[i].i=i;
//		printf("%d : %d\n",i,c[i].t);
	}
	sort(c+1,c+m+1,cmp_by_t);
	int z=1;
	fo(k,0,n*(n+1)/2) {
//		printf("%d : %lld %lld %lld\n",k,s1,s2,f[n][k]);
		ans=minl(ans,f[n][k]+s1+s2);
		while(z<=m&&c[z].t==k) {
			s1-=1ll*k*c[z].i;
			s2+=b[c[z].i];
			si-=c[z].i;
			z++;
		}
		s1+=si;
	}
	wtl(ans);
}

标签:Balls,int,题解,sum,long,leq,Many,ll,define
From: https://www.cnblogs.com/2008verser/p/17904048.html

相关文章

  • CF1784C Monsters (hard version) 题解 线段树
    题目链接:https://codeforces.com/problemset/problem/1784/C题目大意:你面前有\(n\)只怪兽,每只怪兽都有一个初始血量,你可以进行两类操作:操作1:选择任意一个血量大于\(0\)的怪兽,并将它的血量降低\(1\);操作2:将所有存活的怪物的血量各自减去\(1\),如果存在怪物的血量恰好降为......
  • PTA-2023第十三次练习题目题解
    PTA-2023第十三次练习题目题解以下代码已做防抄袭处理,切勿抄袭。注意:手机端因为屏幕限制,代码会有(不希望的)换行。解决方案:1.建议使用电脑端打开。2.点击代码进入全屏观看。6-25实验9_5_反向打印字符串思路就是每次先找到字符串的最后一位,然后输出这一位,输出之后将这一位改为‘......
  • P8818 [CSP-S 2022] 策略游戏 题解
    P8818[CSP-S2022]策略游戏题解题目链接P8818[CSP-S2022]策略游戏简化题意小\(A\)先在\(a[l1,r1]\)中选择一个数\(x\),小\(B\)再在\(b[l2,r2]\)中选择一个数\(y\),最后的分数就是\(x\timesy\)。小\(A\)想让分数尽可能地大,而小\(B\)则想让分数尽可能地小......
  • 【问题解决】unable to do port forwarding: socat not found
    问题复现前阵子应公司要求做华为云平台的调研,写了一篇文档包含将华为云CCE下载kuberctl配置及使用kubectl转发流量到本地的操作。今天一早上同事就发来一个错误界面,说是Java远程调试转发过来的端口出现问题,如下图:处理思路最初以为是容器镜像未安装socat所致,安装重新打镜像后......
  • 12月13日80端口被占用问题解决
    在写软件构造作业的时候,发现Jfinal提示java.lang.IllegalStateException:port:80notavailable!原因是因为我们的80端口被占用了,当我们输入localhost的时候出现的是windows iis服务的界面这个时候需要我们关闭windowsiis服务1.点击开始收索服务,在服务界面找到worldWide......
  • luogu1972题解
    还是先写被卡的做法吧。节点的区间用了现用现计算卡常过了。被卡了一上午,难过。话说有人说我码风有点抽象。思路主席树做法。a[i]是贝壳序列。先求出nxt,即与a[i]相同的下一个a[j]的下标j。用p114514[i]记了值为\(i\)的数的下标,循环到序列第\(j\)个数的时候,先......
  • Vue + Element UI 实现复制当前行数据功能(复制到新增页面组件值不能更新等问题解决)
    1、需求使用Vue+ElementUI实现在列表的操作栏新增一个复制按钮,复制当前行的数据可以打开新增弹窗后亦可以跳转到新增页面,本文实现为跳转到新增页面。2、实现1)列表页index.vue<el-table><!--其他列--><el-table-columnlabel="操作"width="150"><templateslot-scope=......
  • [CF980D] Perfect Groups 题解
    [CF980D]PerfectGroups题解思路第一个观察就很难观察到:\[ab=x^2,bc=y^2\Longrightarrow\existz,ac=z^2(a,b,c\ne0)\]证明:两个条件式相乘得到:\[ab^2c=x^2y^2\\ac=\dfrac{x^2y^2}{b^2}(b\ne0)\\\becauseb|x^2,b|y^2\\\thereforeb^2|x^2y^2......
  • P1004 [NOIP2000 提高组] 方格取数 题解
    P1004[NOIP2000提高组]方格取数题解题目链接P1004[NOIP2000提高组]方格取数简要思路注意一下输入可以简化为while(std::cin>>x>>y>>val&&x){ //***}运用DP的思想。用一个四维的\(DP\)数组\(dp[i][j][k][l]\)来同时记录两条路径分别走到\((i,j)\)和\((k,......
  • P4463 [集训队互测 2012] calc 题解
    Description一个序列\(a_1,a_2,\dots,a_n\)是合法的,当且仅当:\(a_1,a_2,\dots,a_n\)都是\([1,k]\)中的整数。\(a_1,a_2,\dots,a_n\)互不相等。一个序列的值定义为它里面所有数的乘积,即\(a_1\timesa_2\times\dots\timesa_n\)。求所有不同合法序列的值的和对\(p\)......