UVA - 1152 4 Values whose Sum is 0问题分解,二分查找
2024-09-04 12:51:17
题目:点击打开题目链接
思路:暴力循环显然会超时,根据紫书提示,采取问题分解的方法,分成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 ;
}
最新文章
- JS 删除对象属性
- centos6.5 升级安装pcre 8.39版本
- sqlserver存取过程游标
- mysql 触发器的使用(备忘)
- Maven解决Missing artifact com.sun:tools:jar:1.5.0错误
- JavaScript要点 (六) 函数参数
- 如何区分Shapefile,Coverage,Geodatabase(转载)
- 微信jssdk批量展示卡包中的卡券
- c++ iostream 相关使用
- MySQL 常用基础命令
- MySQL主从同步校验与重新同步
- jQuery克隆DOM节点
- 在AWS中部署OpenShift平台
- iOS代码处理横屏问题
- python中csv文件的读取问题
- 解决150%DPI下Photoshop不能显示成合适大小的问题
- jQuery设置时间格式
- HDU 1160
- 微信小游戏 three.js jsonloader request:fail invalid url
- javaSE习题 第一章 JAVA语言概述