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