[Codeforces] CF1857D Strong Vertices

Strong Vertices - 洛谷

题解是个好东西

题意

给定两个数组 \(a\) 和 \(b\)，对此构造一张有向图：

• 若 \(a_u−a_v≥b_u−b_v\)，则 \(u\) 向 \(v\) 连边。

求所有向其他所有顶点连边的顶点个数，并按从小到大顺序输出它们。

思路

先对原式进行转换：\(a_u-b_u\geq a_v-b_v\)

接着，由\(a>b\)且\(b>c\)，则\(a>c\)得到，\(a\)和\(b\)连接，\(b\)和\(c\)连接，但是\(c\)不能和\(a\)连接。故\(a,b\)两个数列一定无环，也就是说\(a\)的入度为\(0\)

在考虑\(a=b\)的情况，这是就是\(a\)和\(b\)之间有一条无向边相连。

综上，得到结论：当一点除了所有与之相连的无向边之外入度为\(0\)，该点符合题目要求（即称作Strong Vertices）

再根据最初的\(a_u-b_u\geq a_v-b_v\)，推出，我们只需要找到\(a_i-b_i\)的最大值，再算出该最大值的出现数量即可。

其实这道题和图基本上八竿子打不着，最多在推导时有点用

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5;
int maxn,n,a[MAXN],b[MAXN];
vector<int>ans;
int run()
{
	cin>>n;maxn=-2e9;ans.clear();
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) cin>>b[i];
	for(int i=0;i<n;i++) maxn=max(maxn,a[i]-b[i]);
	for(int i=0;i<n;i++) if(a[i]-b[i]==maxn) ans.push_back(i+1);
	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}
int main()
{
	int t;
	cin>>t;
	while(t--) run();
	return 0;
}

（好整齐的for