AT-AGC018-C 题解

科技：

wqs 二分（板子）

思路：

首先，

O(n^3)

很好做：
设二维背包

f_{i,j}

，表示金币取

i

个，银币取

j

个，则有：

f_{i,j}=\max(f_{i-1,j}+a,f_{i,j-1}+b,f_{i-1,j-1}+c)

然后，我们不难证明

(i,f_{i,j})

和

(j,f_{i,j})

分别构成两个凸包：
考虑归纳。初始时，只有

f_{0,0}=0

，其余可以视为负无穷，因此满足凸性。再观察转移式本质上就是将三个凸包平移后再取

\max

，显然做完这些操作后我们得到的还是凸包。
因此，我们可以先用 wqs 二分把问题从三维降至二维，变成只限制一种币取的个数。我们不妨限制银币恰好取

y

个，那么，每个人的贡献就变成了

B_i

或

\max(A_i,C_i)

，并且要有恰好

y

个人选

B_i

。
这个问题简单贪心即可：我们可以把所有人按

B_i-max(A_i,C_i)

排序，前

y

大的人选

B_i

，后面的人都选

max(A_i,C_i)

。

代码：

CPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 1e5 + 5;
int n,x,y,z,cnt,a[N],b[N],c[N];
struct Node{int w1,w2,t;} p[N];
bool cmp(Node x,Node y)
{
	if(x.w2 - x.w1 != y.w2 - y.w1) return x.w2 - x.w1 > y.w2 - y.w1;
	return x.t < y.t;
}
ll check(int k)
{
	ll ret = 0;
	cnt = 0;
	for(int i = 1;i <= n;i++)
	{
		if(a[i] - k >= c[i]) p[i].w1 = a[i] - k,p[i].t = 1;
		else p[i].w1 = c[i],p[i].t = 0;
		p[i].w2 = b[i];
	}
	sort(p + 1,p + n + 1,cmp);
	for(int i = 1;i <= y;i++) ret += p[i].w2;
	for(int i = y + 1;i <= n;i++) ret += p[i].w1,cnt += p[i].t;
	return ret;
}
int main()
{
	scanf("%d%d%d",&x,&y,&z);
	n = x + y + z;
	for(int i = 1;i <= n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
	int l = -1e9,r = 1e9,mid;
	while(r - l > 1)
	{
		mid = ((l + r) >> 1);
		check(mid);
		if(cnt >= x) l = mid;
		else r = mid;
	}
	printf("%lld\n",check(l) + 1LL * l * x);
	return 0;
}

文章操作

科技：

思路：

代码：

相关推荐

评论

AT-AGC018-C 题解