专栏文章

题解：AT_agc034_c [AGC034C] Tests

CCQ_JiJi
AT_agc034_c题解参与者 1已保存评论 0

文章操作

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

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

Solution\text{Solution}

看题解区都是二分的方法，这样的复杂度是 O(nlog⁡V)O(n\log V) 的，这里提供一种 O(nlog⁡n)O(n\log n) 的，时间复杂度在于排序。
考虑贪心，首先，假设已知最终高桥君的每科分数，那么对于分数比青木君大的场，ci←ric_i\gets r_i，否则 ci←lic_i\gets l_i。这是显然的。然后容易发现不存在 i,ji,j，使得 ai≠0,ai≠Xa_i\neq 0,a_i\neq X 且 aj≠0,aj≠Xa_j\neq 0,a_j\neq X。
显然若存在这样的 i,ji,j，一定可以将 cc 值小的一个的分数给到，cc 值大的一个。
那么有了这个性质，我们就可以先计算初始状态下青木君的总得分 sumsum，即 ∑i=1i=nlibi\sum\limits_{i=1}^{i=n}l_ib_i，那么考虑高桥君将 ii 场考试学到 XX 分的贡献，首先会抵消掉青木君的贡献，然后在 ai>bia_i>b_i 时，将 cic_i 改为 rir_i，则总贡献 wiw_i 为 libi+ri(X−bi)l_ib_i+r_i(X-b_i)，将序列以这个值为关键字排序排序，可以求出一个最小的 ii 使得 ∑j=1iwj≥sum\sum\limits_{j=1}^{i}w_j \geq sum，分两种情况讨论：
1.若唯一的不为 00 且不为 XX 的位置 jj 是 [i,n][i,n] 中的，那么记 res←sum−∑k=1i−1wkres\gets sum-\sum\limits_{k=1}^{i-1}w_k。先判断能否在 bjb_j 个以内完成超越，即 ljbj≥resl_jb_j\geq res，此时答案为 ⌈reslj⌉\lceil \frac{res}{l_j}\rceil，否则答案为 bj+⌈res−ljbjlj⌉b_j+\lceil \frac{res-l_jb_j}{l_j}\rceil。
2.若唯一的不为 00 且不为 XX 的位置 jj 是 [1,i)[1,i) 中的，得先去除掉该位置的贡献并补上 ii 位置的贡献，即 res←sum−(∑k=1i−1wk−wj+wi)res\gets sum-(\sum\limits_{k=1}^{i-1}w_k-w_j+w_i)，剩下的过程与第一种情况一样。
CPP
/*
	Luogu name: Symbolize
	Luogu uid: 672793
*/
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(register int i=l;i<=r;++i)
#define rep2(i,l,r) for(register int i=l;i>=r;--i)
#define rep3(i,x,y,z) for(register int i=x[y];~i;i=z[i])
#define rep4(i,x) for(auto i:x)
#define debug() puts("----------")
const int N=2e6+10;
const int inf=0x3f3f3f3f3f3f3f3f;
using namespace std;
int n,x;
struct node
{
	int b;
	int l,r;
	int w;
}a[N];
bool cmp(node a,node b){return a.w>b.w;}
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f*x;
}
signed main() 
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=read();
	x=read();
	int sum=0;
	rep1(i,1,n)
	{
		a[i].b=read();
		a[i].l=read();
		a[i].r=read();
		a[i].w=(x-a[i].b)*a[i].r+a[i].b*a[i].l;
		sum+=a[i].b*a[i].l;
	}
	sort(a+1,a+n+1,cmp);
	rep1(i,1,n)
	{
		if(sum-a[i].w<=0)
		{
			int ans=inf;
			rep1(j,i,n) 
			{
				if(sum-a[j].b*a[j].l<=0) ans=min(ans,(sum+a[j].l-1)/a[j].l);
				else ans=min(ans,a[j].b+(sum-a[j].b*a[j].l+a[j].r-1)/a[j].r);
			}
			rep1(j,1,i-1)
			{
				int now=sum+a[j].w-a[i].w;
				if(now-a[i].w<=0) 
				{
					if(now-a[j].b*a[j].l<=0) ans=min(ans,(now+a[j].l-1)/a[j].l);
					else ans=min(ans,a[j].b+(now-a[j].b*a[j].l+a[j].r-1)/a[j].r);
				}
			}
			cout<<(i-1)*x+ans<<"\n";
			return 0;
		}
		sum-=a[i].w;
	}
    return 0;
}

评论

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

正在加载评论...