2023 提高实战营-秋专题测试 01

A. 寇德佛斯

题目链接

简要思路

对于题目 \(i\) 和题目 \(j\)，假设当前开始了 \(w\) 时间，如果先做 \(i\) 再做 \(j\)，那么得到的分数将会是 \(s_i - (w + t_i) · v_i + s_j -(w + t_i +t_j) · v_j\)，最后整理一下可得时先做题目 \(i\) 再做题目 \(j\)，当且仅当 \(t_i · v_j < t_j · v_i\) 成立，所以我们只需按照该式子进行排序，然后遍历计算即可。

完整代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int MAXN=1e6+5;

int n;
int ans,w;
struct node{
	int s,v,t;
}a[MAXN];

bool cmp(node x,node y){return y.t*x.v>x.t*y.v;}//排序的方法

signed main(){
	std::cin>>n;
	for(int i=1;i<=n;i++)
		std::cin>>a[i].s>>a[i].v>>a[i].t;
	std::sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		w+=a[i].t;//先更新做题的时间 w
		ans+=a[i].s-w*a[i].v;
	}
	std::cout<<ans<<endl;
	return 0;
}

B. 跑步比赛

题目链接

B. 跑步比赛

简要思路

读完题面后我们可以提炼出一个关键词：要使最小值最大，因此我们可以二分答案。

对于二分到的一个 \(x\)，我们以 \(x\) 为基准，把全部队员分为两个部分：\(v_i \ge x\) 的队员（即可以背负其他队员的队员）和 \(v_i < x\) 的队员（即需要被其他队员背负的队员）。

因为一个队员最多只能背负一个队员，所以当需要被背负的队员的数量大于可以背负其他队员的队员的数量时，check 函数可以直接返回 false。

一个队员 \(i\) 可以背负队员 \(j\)，当且仅当 \(v_i - (w_j - w_i) \ge x\) 成立。

不难想到，最快最重的队员一定要背负最慢最重的队员，但是我们发现，上述式子中 \(v_j\) 并不影响最终的结果，所以我们只考虑 \(w_i,v_i,w_j\)。

由此，我们将可以背负其他队员的队员的数组按照体重和速度之和从大到小进行排序，对需要被其他队员背负的队员的数组按照体重从大到小进行排序。之后遍历数组，如果不满足 \(v_i - (w_j - w_i) \ge x\) 就返回 false，否则最终返回 true。

完整代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
const int MAXN=1e5+5;

int T,n;
int v[MAXN],w[MAXN];
int a[MAXN];//可以背负其他队员的队员
int b[MAXN];//需要被其他队员背负的队员

bool cmpa(int a,int b){return (w[a]+v[a])>(w[b]+v[b]);}
bool cmpb(int a,int b){return w[a]>w[b];}

bool check(int x){
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));//多测不清空，爆零两行泪！
	int cnta=0,cntb=0;//统计各组队员的数量
	for(int i=1;i<=n;i++){
		if(v[i]>=x)a[++cnta]=i;//可以背负其他队员，记录编号
		else b[++cntb]=i;//需要被其他队员背负，记录编号
	}
	
	if(cnta<cntb)return false;//人数太多
	
	std::sort(a+1,a+cnta+1,cmpa);
	std::sort(b+1,b+cntb+1,cmpb);
	
	for(int i=1;i<=cntb;i++){//上文的 if 判断已经确保了 cnta>=cntb
		int now=v[a[i]]-(w[b[i]]-w[a[i]]);
		if(now<x)return false;//看能否达到二分所需要的速度 x
	}
	return true;
}

signed main(){
	std::cin>>T;
	while(T--){
		std::cin>>n;
		for(int i=1;i<=n;i++)std::cin>>v[i]>>w[i];
		
		int l=1,r=1e9;
		while(l<r){//二分答案
			int mid=(l+r+1)/2;
			if(check(mid))l=mid;
			else r=mid-1;
		}
		std::cout<<l<<endl;
	}
	
	return 0;
}