首页 > 代码库 > hdu--2578--与女孩约会
hdu--2578--与女孩约会
杭电的这个出题人真闷骚啊....
冠以 与女孩约会的名义 出了这么个
这题 不难的 但是一定要读懂题目意思
Two solutions are different if x0 != x1 or y0 != y1.
这就告诉我们 1+3=4 与 3+1=4 这是2种方法
但是如果那个古怪的女孩给了你1 1 1 3
你可能会上当以为就有6种了 因为不是有3个1嘛... 但其实还是2种 因为 1+3 和 1+3是相同的
女孩的心思 你能懂？
其实 我们变形下这题 如果1 1 1 3是6种的话
我的做法是开个hash数组或者map来记录下个数 同时还是要进行Unique操作
因为 用我的双指针做法的时候 如果你不进行unique操作 会变得有些复杂
假设给你数据1 1 3 3
首先指针分别指向首尾 然后1+3 = 4 OK符合条件 然后指针进行移动..那该怎么移动呢？
如果再来组数据1 3 3 3 和 1 1 1 3呢？
找不到一个好的处理方案
但如果存在了hash或map之中的话 只要 hash[*st] * hash[*end] * 2就可以了
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 const int size = 100010; 6 int arr[size]; 7 8 int main() 9 {10 cin.sync_with_stdio(false);11 int t , n , k , ans;12 int* st;13 int* end;14 cin >> t;15 while(t--)16 {17 cin >> n >> k;18 for( int i = 0 ; i<n ; i++ )19 {20 cin >> arr[i];21 }22 sort(arr,arr+n);23 st = arr;24 end = unique(arr,arr+n);25 end -= 1;26 ans = 0;27 while( st<=end )28 {29 if( *st == *end && *st + *end == k )30 {31 ans ++;32 st ++;33 end --;34 }35 else if( *st + *end == k )36 {37 ans +=2;38 st ++;39 end --; 40 }41 else if( *st + *end > k )42 {43 end --;44 }45 else46 {47 st ++;48 }49 }50 cout << ans << endl;51 }52 return 0;53 }
这题 discuss里也有人直接用Map做 当然也很好 因为map直接只能保存每个元素1次 省去了Unique操作 但同时 这边数据很大 2^31-1达到 我觉得map这样建树并不快
3天以来的第一题.... 玩mhxy伤神啊
hdu--2578--与女孩约会
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。