D. Strong Vertices - 思维 + 二分

 

 

 分析：

        首先找到边的指向很容易，但是暴力是o(n2），超时，可以将给定的式子变形，au - av >= bu - bv即au - bu >= av - bv，可以将两个数组转变为一个数组中的任意两个值之间的关系，因此可以遍历整个数组，在其中二分查找每一个符合条件的数，就可以优化时间复杂度。

代码：

#include <bits/stdc++.h>using namespace std;
using ll = long long;typedef pair<ll,int> pii;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while(T --) {int n;cin >> n;vector<pii> a(n);vector<ll> b(n);for(int i=0;i<n;i++) cin>>a[i].first;for(int i=0;i<n;i++) cin>>b[i];vector<int> x(n+1);for(int i=0;i<n;i++) {a[i].first-=b[i];a[i].second = i+1;}// for(int i=0;i<a.size();i++) cout<<a[i].first<<' ';//     cout<<endl;sort(a.begin(),a.end());//for(int i=0;i<a.size();i++) cout<<a[i].first<<' ';//     cout<<endl;for(int i=0;i<a.size();i++) {int l=0;int r=a.size()-1;while(l<r) {int mid=(l+r+1)/2;if(a[mid].first<=a[i].first) l=mid;else r=mid-1;}x[a[i].second]=l;//  cout<<a[i].second << ' ' <<l<<endl;}vector<int> ans;for(int i=1;i<=n;i++) {// cout<<x[i]<<' ';if(x[i]==n-1) ans.push_back(i);}cout<<ans.size()<<'\n';for(int i=0;i<ans.size();i++) cout<<ans[i]<<' ';cout<<'\n';}
}