题目:点击打开题目链接

思路:暴力循环显然会超时,根据紫书提示,采取问题分解的方法,分成A+B与C+D,然后采取二分查找,复杂度降为O(n2logn)

AC代码:

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 int main()
{
ios::sync_with_stdio(false);
cin.tie();
int T, n, ans; cin >> T;
int A[maxn], B[maxn], C[maxn], D[maxn];
while(T--) {
ans = ; vector<int> vec;
cin >> n;
for(int i = ; i < n; ++i) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
} for(int i = ; i < n; i++)
for(int j = ; j < n; j++)
vec.push_back(A[i] + B[j]);
sort(vec.begin(), vec.end()); for(int i = ; i < n; i++)
for(int j = ; j < n; j++)
ans += upper_bound(vec.begin(), vec.end(), -(C[i] + D[j])) - lower_bound(vec.begin(), vec.end(),-(C[i] + D[j])); cout << ans << endl;
if(T) cout << endl;
}
return ;
}

最新文章

  1. JS 删除对象属性
  2. centos6.5 升级安装pcre 8.39版本
  3. sqlserver存取过程游标
  4. mysql 触发器的使用(备忘)
  5. Maven解决Missing artifact com.sun:tools:jar:1.5.0错误
  6. JavaScript要点 (六) 函数参数
  7. 如何区分Shapefile,Coverage,Geodatabase(转载)
  8. 微信jssdk批量展示卡包中的卡券
  9. c++ iostream 相关使用
  10. MySQL 常用基础命令
  11. MySQL主从同步校验与重新同步
  12. jQuery克隆DOM节点
  13. 在AWS中部署OpenShift平台
  14. iOS代码处理横屏问题
  15. python中csv文件的读取问题
  16. 解决150%DPI下Photoshop不能显示成合适大小的问题
  17. jQuery设置时间格式
  18. HDU 1160
  19. 微信小游戏 three.js jsonloader request:fail invalid url
  20. javaSE习题 第一章 JAVA语言概述

热门文章

  1. 《java学习二》并发编程
  2. java lombok包在maven已经配置,但是注解没用
  3. mysql通过sql语句判断某个字段在一张表中是否存在
  4. Windows下用cpu模式跑通目标检测py-faster-rcnn 的demo.py
  5. Mysql一个表编码的坑,mark一下
  6. wepy开发踩坑记录
  7. Java选择排序算法
  8. FastDFS整合Nginx
  9. java http的get,post请求
  10. uvm_reg_cbs——寄存器模型(十六)