uva 11386 Triples （hash總是wa,於是模擬STL）

uva 11386 Triples 這題 應該用 hash , 用 STL map超時，但是我自己手寫二分，再加一些優化，限時8秒，我7.8秒卡過，很爽！

這題彈了很多遍，注意的是，ans 用int 不夠，最後直接改為long long  就過了，因為這題數據沒說范圍，只說了是正整數，所以有點不爽啊。。。但是，ans可以算出來絕對超過 int 的 ，因為最多5000個數，如果有1000個1  1000個2  3000個3 答案就是  3e9 超過int 了

#include <iostream>  
#include <cstdio>   
#include <map>  
#include <vector>  
#include <algorithm>  
using namespace std; 
 
const int maxn=5010; 
long long a[maxn],n; 
map <long long,int> mp; 
map <long long,int>::iterator it; 
vector <long long> v; 
vector <int> cnt; 
 
int binaryS(int left,int c){ 
    int l=left,r=v.size()-1; 
    while(l<r){ 
        int mid=(l+r)/2; 
        if(v[mid]>=c) r=mid;  
        else l=mid+1; 
    } 
    return r; 
} 
 
int main(){ 
    while(scanf("%d",&n)!=EOF){ 
        long long int ans=0; 
        mp.clear();v.clear();cnt.clear(); 
        for(int i=0;i<n;i++){ 
            scanf("%lld",&a[i]); 
            mp[a[i]]++; 
        } 
        for(it=mp.begin();it!=mp.end();it++){ 
            v.push_back(it->first); 
            cnt.push_back(it->second); 
        } 
        sort(a,a+n); 
        for(int i=0;i<n;i++){ 
            int left=0; 
            for(int j=i+1;j<n;j++){ 
                long long sum=a[i]+a[j]; 
                int pos=binaryS(left,sum); 
                if(v[pos]!=sum) continue; 
                ans+=cnt[pos]; 
                left=max(pos-1,left); 
            } 
        } 
        cout<<ans<<endl; 
    } 
    return 0; 
}  

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn=5010;
long long a[maxn],n;
map <long long,int> mp;
map <long long,int>::iterator it;
vector <long long> v;
vector <int> cnt;

int binaryS(int left,int c){
 int l=left,r=v.size()-1;
 while(l<r){
  int mid=(l+r)/2;
  if(v[mid]>=c) r=mid;
  else l=mid+1;
 }
 return r;
}

int main(){
 while(scanf("%d",&n)!=EOF){
  long long int ans=0;
  mp.clear();v.clear();cnt.clear();
  for(int i=0;i<n;i++){
   scanf("%lld",&a[i]);
   mp[a[i]]++;
  }
  for(it=mp.begin();it!=mp.end();it++){
   v.push_back(it->first);
   cnt.push_back(it->second);
  }
  sort(a,a+n);
  for(int i=0;i<n;i++){
   int left=0;
   for(int j=i+1;j<n;j++){
    long long sum=a[i]+a[j];
    int pos=binaryS(left,sum);
    if(v[pos]!=sum) continue;
    ans+=cnt[pos];
    left=max(pos-1,left);
   }
  }
  cout<<ans<<endl;
 }
 return 0;
}