首页 > 代码库 > hdu--4334-双指针
hdu--4334-双指针
这个方法其实 蛮常用的
一般给你3个集合 然后让你满足某个等式 a[x]+b[y] = c[z]
我们通常都是枚举一个集合 然后用两个指针分别指向另外2个集合中的一头一尾 然后进行大小比较来 指针移动
当然 这也是和 二分一样建立在 有序的基础之上进行的
这题 用这个方法解决 就可以了
当然 二分也可以
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 int n; 6 const int size = 210; 7 typedef __int64 LL; 8 LL sum1[size*size] , sum2[size*size] , sum3[size]; 9 LL a[10][size];10 11 bool solve( )12 {13 bool flag = false;14 for( int i = 0 ; i<n ; i++ )15 {16 LL* st = sum1;17 LL* end = sum2 + n*n-1 ;18 while( st<=sum1+n*n-1 && end>=sum2 )19 {20 if( *st + *end + sum3[i] == 0 )21 {22 flag = true;23 break;24 }25 else if( *st + *end + sum3[i] < 0 )26 {27 ++ st;28 }29 else30 {31 -- end;32 }33 }34 if( flag )35 {36 break;37 }38 }39 return flag;40 }41 42 int main()43 {44 cin.sync_with_stdio(false);45 int t , cnt , tot;46 bool ans;47 cin >> t;48 while( t-- )49 {50 cin >> n;51 for( int i = 1 ; i<=5 ; i++ )52 {53 for( int j = 1 ; j<=n ; j++ )54 {55 cin >> a[i][j];56 }57 }58 tot = 0;59 for( int j = 1 ; j<=n ; j++ )60 {61 for( int k = 1 ; k<=n ; k++ )62 {63 sum1[tot++] = a[1][j] + a[2][k];64 }65 }66 tot = cnt = 0;67 for( int j = 1 ; j<=n ; j++ )68 {69 for( int k = 1 ; k<=n ; k++ )70 {71 sum2[tot++] = a[3][j] + a[4][k];72 }73 sum3[cnt++] = a[5][j];74 }75 sort( sum1 , sum1+n*n );76 sort( sum2 , sum2+n*n );77 ans = solve( );78 if( ans )79 cout << "Yes" << endl;80 else81 cout << "No" << endl;82 }83 return 0;84 }
today:
约你出来
你不出来
放我鸽子
hdu--4334-双指针
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。