国内优秀网站欣赏,厦门建设厅网站,武进网站建设基本流程,广西城乡和建设厅网站首页分析#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;}
}
