4 Values whose Sum is 0 POJ - 2785

本文主要是介绍4 Values whose Sum is 0 POJ - 2785，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题传送门

思路：因为防止超时只能采取折半枚举法；合并c+d到sum数组，合并a+b，然后从sum数组找到对应的值

#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm> 
#include <cstring>
const int MAX = 4010;
const int INF = 1e6;
const int g = 10;using namespace std;int n;
int a[MAX], b[MAX], c[MAX], d[MAX];
int sum[MAX*MAX];//算出右侧和放入sum数组排序 算出左侧和 从sum找个数
void Solve(){//右侧计算 int ans = 0;fill(sum, sum+n*n, 0);for(int i=0; i<n; i++)for(int j=0; j<n; j++)sum[i*n+j] = c[i] + d[j];sort(sum,sum+n*n);//左侧计算后从 b 找 for(int i=0; i<n; i++)for(int j=0; j<n; j++){int cd = a[i] + b[j];ans += upper_bound(sum,sum+n*n,-cd) - lower_bound(sum,sum+n*n,-cd);}			cout << ans << endl;
} //测试函数 
int main(){ifstream cin ("D:\\钢铁程序员\\程序数据\\070四值和总数.txt");//从文件读取数据流，省去手动输入的麻烦 if(!cin){//读取如果失败 cout << "ERROR" << endl;}cin >> n;for(int i=0; i<n; i++)cin >> a[i] >> b[i] >> c[i] >> d[i];Solve();cin.close();//打开文件以后要关闭 return 0;
} 

 

这篇关于4 Values whose Sum is 0 POJ - 2785的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---