CF1857D 讲解

CheZiHe929 / 2023-08-08 / 原文

CF1857D

原题链接

Codeforces

洛谷

题目翻译

见原题。

简要题面

给你两个数组 a 和 b，通过以下规则建边：
如果 \(a_u-a_v \ge b_u-b_v\)，那么就建一条从 \(u\) 到 \(v\)（\(u \not= v\)）的有向边。

问能到达所有顶点的点（题目中称为强顶点，即出度为 \(n - 1\) 的点）的数量，并按升序输出他们。

简要思路

从 \(a_u-a_v \ge b_u-b_v\) 下手，通过不等式的移项原则进行移项，得到 \(a_u - b_u \ge a_v - b_v\)。

因此我们只需要记录一个数组 a_b[i] = a[i] - b[i]，然后对其进行排序，所谓的求强顶点就是看有几个最大值。

最后我们遍历一下整个数组，看有几个的值等于最大值，并记录在 ans 数组内，最后输出即可（从小到大遍历保证升序）。

完整代码

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

int a[MAXN],b[MAXN];//题目给定的
int a_b[MAXN];//计算差值
int ans[MAXN];//记录强顶点个数
int t,n;

signed main(){
	cin>>t;
	while(t--){
		cin>>n;

		for(int i=1;i<=n;i++)cin>>a[i];

		int maxn=-2e9;
		//这里注意 maxn 的初始值不能定义为 -1e9，因为存在：a[i]=-1e9 b[i]=1e9 这样 a[i]-b[i] 就会比 1e9 还小
		for(int i=1;i<=n;i++){
			cin>>b[i];
			a_b[i]=a[i]-b[i];//计算差值
			maxn=max(maxn,a_b[i]);//计算当前最大值
		}

		int cnt=0;//强顶点个数
		for(int i=1;i<=n;i++)
			if(a_b[i]==maxn)ans[++cnt]=i;//是强顶点

		cout<<cnt<<'\n';
		for(int i=1;i<=cnt;i++)//按升序输出
			cout<<ans[i]<<" \n"[i==cnt];
	}
	return 0;
}