4 Values whose Sum is 0
题目链接:https://cn.vjudge.net/problem/UVA-1152
——每天在线,欢迎留言谈论。
题目大意:
给定4个n(1<=n<=4000)元素的集合 A、B、C、D ,从4个集合中分别选取一个元素a, b,c,d。求满足 a+b+c+d=0的对数。
思路:
直接分别枚举 a,b,c,d ,坑定炸了。我们先枚举 a+b并储存,在B、C中枚举找出(-c-d)后进行比较即可。
亮点:
由于a+b,中会有值相等的不同组合,如果使用map来存,很遗憾超时(虽然时间限制是9000ms)。
在一个有序数组求某元素数出现的个数:n = upper_bound(a,a+n,k)-lower_bound(a,a+n,k) ;
C++ AC代码:
#include <iostream>
#include <cmath>
#include <iostream>
#include <string>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
const int INT_INF = 0x3f3f3f3f;
const double EPS = 1e-;
typedef long long ll;
const int MAXN = 4e3+;
int numbers[][MAXN],sumAB[MAXN*MAXN];
int main()
{
int t;
cin>>t;
while(t--)
{
memset(numbers,,sizeof(numbers));
memset(sumAB,INT_INF,sizeof(sumAB));
int n,p1=,p2=;
cin>>n;
for(int i=;i<n;i++)
for(int j=;j<;j++)
cin>>numbers[j][i];
for(int i=;i<n;i++)
for(int j=;j<n;j++)
sumAB[p1++]=numbers[][i]+numbers[][j];
sort(sumAB,sumAB+p1);
int answer=;
for(int i=;i<n;i++)
for(int j=;j<n;j++)
{
answer+=upper_bound(sumAB,sumAB+p1,-numbers[][i]-numbers[][j])-lower_bound(sumAB,sumAB+p1,-numbers[][i]-numbers[][j]);
}
cout<<answer<<endl;
if(t)
cout<<endl;
}
return ;
}
Java AC代码:
import java.util.Scanner;
public class Main {
static Scanner scn = new Scanner(System.in); static final int MAXN = 4100;
static int[][] numbers = new int[4][MAXN];
static int[] sumAB = new int[MAXN*MAXN];
public static void main(String[] args) {
int t;
t = scn.nextInt();
while ((t--) > 0) {
int n;
n = scn.nextInt();
for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
numbers[j][i] = scn.nextInt();
}
}
int p1 = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sumAB[p1++] = numbers[0][i] + numbers[1][j];
}
}
Tool.quickSort(sumAB,0,p1-1);
//输出看看
// for (int i = 0; i < p1; i++) {
// System.out.print(sumAB[i] + " ");
// } //成功
//开始枚举-c-d
int answer = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
answer += Tool.uppper(sumAB, 0, p1, -numbers[2][i] - numbers[3][j]) - Tool.lower(sumAB, 0, p1, -numbers[2][i] - numbers[3][j]);
}
}
System.out.println(answer);
if(t > 0)
System.out.println();
}
System.exit(0);
}
}
class Tool {
public static int lower(int[] array, int low, int high, int number) {
//[low,high)
int i = low, j = high, m;
while (i < j) {
m = i + (j - i) / 2;
if (array[m] >= number)
j = m;
else
i = m+1;
}
return i;
}
public static int uppper(int[] array, int low, int high, int number) {
int i = low, j = high, m;
while (i < j) {
m = i + (j - i) / 2;
if (array[m] <= number)
i = m+1;
else
j = m;
}
return i;
}
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int m = partition(array, low, high);
quickSort(array, low, m-1);
quickSort(array, m+1, high);
}
}
private static int partition(int[] array, int low, int high) {
int mNumber = array[low];
int i = low, j = high;
while (i < j) {
while (i < j && array[j] >= mNumber) {--j;}
array[i] = array[j];
while (i < j && array[i] <= mNumber) {++i;}
array[j] = array[i];
}
array[i] = mNumber;
return i;
}
}
2017-07-30 11:06:43 -> 2017-07-30 13:45:32