北京建站公司哪个好,定制网站建设托管,先做网站 先备案,高明区做网站分析#xff1a; 首先找到边的指向很容易#xff0c;但是暴力是o(n2#xff09;#xff0c;超时#xff0c;可以将给定的式子变形#xff0c;au - av bu - bv即au - bu av - bv#xff0c;可以将两个数组转变为一个数组中的任意两个值之间的关系#xff0c;因… 分析 首先找到边的指向很容易但是暴力是o(n2超时可以将给定的式子变形au - av bu - bv即au - bu av - bv可以将两个数组转变为一个数组中的任意两个值之间的关系因此可以遍历整个数组在其中二分查找每一个符合条件的数就可以优化时间复杂度。
代码
#include bits/stdc.husing namespace std;
using ll long long;typedef pairll,int pii;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin T;while(T --) {int n;cin n;vectorpii a(n);vectorll b(n);for(int i0;in;i) cina[i].first;for(int i0;in;i) cinb[i];vectorint x(n1);for(int i0;in;i) {a[i].first-b[i];a[i].second i1;}// for(int i0;ia.size();i) couta[i].first ;// coutendl;sort(a.begin(),a.end());//for(int i0;ia.size();i) couta[i].first ;// coutendl;for(int i0;ia.size();i) {int l0;int ra.size()-1;while(lr) {int mid(lr1)/2;if(a[mid].firsta[i].first) lmid;else rmid-1;}x[a[i].second]l;// couta[i].second lendl;}vectorint ans;for(int i1;in;i) {// coutx[i] ;if(x[i]n-1) ans.push_back(i);}coutans.size()\n;for(int i0;ians.size();i) coutans[i] ;cout\n;}
}
