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就可以了

#include <iostream>
#include <algorithm>
using namespace std;

const int size = 100010;
int arr[size];

int main()
{
    cin.sync_with_stdio(false);
    int t , n , k , ans;
    int* st;
    int* end;
    cin >> t;
    while(t--)
    {
        cin >> n >> k;
        for( int i = 0 ; i<n ; i++ )
        {
            cin >> arr[i];
        }
        sort(arr,arr+n);
        st = arr;
        end = unique(arr,arr+n);
        end -= 1;
        ans = 0;
        while( st<=end )
        {
            if( *st == *end && *st + *end == k )
            {
                ans ++;
                st ++;
                end --;
            }
            else if( *st + *end == k )
            {
                ans +=2;
                st ++;
                end --;    
            }
            else if( *st + *end > k )
            {
                end --;
            }
            else
            {
                st ++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

这题 discuss里也有人直接用Map做 当然也很好 因为map直接只能保存每个元素1次 省去了Unique操作 但同时 这边数据很大 2^31-1达到 我觉得map这样建树并不快

3天以来的第一题.... 玩mhxy伤神啊