Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3954 Accepted Submission(s): 1228
题解：取两个数使得x+y=k;因为就两个数，所以用二分，set，map均可，若取多个的和是k就要考虑动态规划了，前面做过，上代码：
二分：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; #define mem(x,y) memset(x,y,sizeof(x)) const int INF=0x3f3f3f3f; const double PI=acos(-1.0); const int MAXN=100010; int m[MAXN],k; bool erfen(int l,int r,int x){ int mid; while(l<=r){ mid=(l+r)>>1; if(x+m[mid]==k){ // printf("%d %d\n",x,m[mid]); return true; } if(x+m[mid]>=k)r=mid-1; else l=mid+1; } return false; } int main(){ int T,n; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",m+i); m[0]=-INF; sort(m,m+n+1); int cnt=0; for(int i=1;i<=n;i++){ if(m[i]>k||m[i]==m[i-1])continue; if(erfen(1,n,m[i]))cnt++; } printf("%d\n",cnt); } return 0; }
map：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<map> 7 const int INF=0x3f3f3f3f; 8 using namespace std; 9 const int MAXN=100010; 10 map<int,int>mp; 11 int m[MAXN]; 12 int main(){ 13 int T,n,k; 14 scanf("%d",&T); 15 while(T--){ 16 mp.clear(); 17 scanf("%d%d",&n,&k); 18 m[0]=-INF; 19 for(int i=1;i<=n;i++){ 20 scanf("%d",m+i); 21 if(!mp[m[i]]) 22 mp[m[i]]=1; 23 else i--,n--; 24 // cout<<m[i]<<mp[m[i]]<<endl; 25 } 26 int cnt=0; 27 for(int i=1;i<=n;i++){ 28 if(m[i]>k)continue; 29 if(mp[k-m[i]])cnt++; 30 } 31 printf("%d\n",cnt); 32 } 33 return 0; 34 }
set：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<set> 7 const int INF=0x3f3f3f3f; 8 using namespace std; 9 const int MAXN=100010; 10 set<int>st; 11 int m[MAXN]; 12 int main(){ 13 int T,n,k,temp; 14 scanf("%d",&T); 15 while(T--){ 16 st.clear(); 17 scanf("%d%d",&n,&k); 18 for(int i=0;i<n;i++){ 19 scanf("%d",&temp); 20 st.insert(temp); 21 } 22 set<int>::iterator iter; 23 int cnt=0; 24 for(iter=st.begin();iter!=st.end();iter++) 25 if(st.count(k-*iter))cnt++; 26 printf("%d\n",cnt); 27 } 28 return 0; 29 }
Dating with girls(1)(二分+map+set)
原文：http://www.cnblogs.com/handsomecui/p/4918129.html