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;
}

补充：软件开发 , C++ ,