hdu 4334 Trouble 排序+优化 多校联合赛(四)第四题
来源:岁月联盟
时间:2012-08-05
设x为s1的头,y为s2的尾,然后对每一个a5进行比较,如果(s1[x]+s2[y]+a5[i]<0) x++; else if((a[x]+b[y]+c[i])>0) y--; 时间复杂都为n^3,其实这样做快是因为排序后避免的很多没有必要的比较
[cpp]
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 205
__int64 a[N*N],b[N*N],c[N];
int main(){
__int64 t,n,x,y;
scanf("%I64d",&t);
while(t--){
int cou=0;
scanf("%I64d",&n);
for(int i=0;i<n;i++)
scanf("%I64d",&c[i]);
for(int i=0;i<n;i++){
scanf("%I64d",&x);
for(int j=0;j<n;j++){
a[cou++]=x+c[j];
}
}
cou=0;
for(int i=0;i<n;i++)
scanf("%I64d",&c[i]);
for(int i=0;i<n;i++){
scanf("%I64d",&x);
for(int j=0;j<n;j++){
b[cou++]=x+c[j];
}
}
for(int i=0;i<n;i++)
scanf("%I64d",&c[i]);
sort(a,a+cou);
sort(b,b+cou);
// cout<<"***"<<endl;
int flag=0;
for(int i=0;i<n;i++){
x=0;y=cou-1;
while(x<cou&&y>=0){
if(a[x]+b[y]+c[i]<0) x++;
else if((a[x]+b[y]+c[i])>0) y--;
else {
flag=1;
break;
}
}
if(flag==1)
break;
}
if(flag) printf("Yes/n");
else printf("No/n");
}
}
作者:youngyangyang04