原题分类于排序 大部分人用二分查找&排序即可AC 用了vector和set 参考另一篇 Ananagrams UVa156的思想 在输入 匹配上可以提高效率
#include <iostream> #include <cstdio> #include <sstream> #include <set> #include <bitset> #include <queue> #include <stack> #include <list> #include <vector> #include <map> #include <string> #include <cstring> #include <cmath> #include <algorithm> using namespace std; typedef set<int> Set; typedef vector<int> Vec; typedef set<int>::iterator It; typedef long long ll; #define mem(s,n) memset(s,n,sizeof(s)) int main(int argc, char *argv[]) { Set s;Vec v; int K,N,temp; scanf("%d%d",&K,&N); while(N--) { scanf("%d",&temp); if(!s.empty()&&s.find(temp)!=s.end()) { v.push_back(temp); v.push_back(K-temp); s.erase(temp);//匹配到则erase } else s.insert(K-temp); } sort(v.begin(),v.end()); if(!v.empty()) for(int i=0;i<v.size()/2;i++) printf("%d %d\n",v[i],K-v[i]); else printf("No Solution\n"); return 0; }可以看出主要是sort和 读取时处理 花了不少时间 还有另一种思路复杂度相似
#include <iostream> #include <cstdio> #include <sstream> #include <set> #include <bitset> #include <queue> #include <stack> #include <list> #include <vector> #include <map> #include <string> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define ll long long #define mem(s,n) memset(s,n,sizeof(s)) #define Set set<int> #define Vec vector<int> int main(int argc, char *argv[]) { int K,N,a[50010]; scanf("%d%d",&K,&N); for(int i=0;i<N;i++) { scanf("%d",&a[i]); if(a[i]>=K/2) a[i]=K-a[i];// } int bad=1,ans=0; sort(a,a+N); for(int i=0;i<N-1;i+=2) if(a[i]==a[i+1]) { printf("%d %d\n",a[i],K-a[i]); bad=0; } if(bad) printf("No solution\n"); return 0; }仍有更好的奇技淫巧
#include <stdio.h> #include <algorithm> using namespace std; const int N = 50005; int k, n; int a[N]; int main() { int i, j; scanf("%d %d", &k, &n); for (i = 0; i < n; i++) { scanf("%d", &a[i]); } sort(a, a + n); bool flag = false; i = 0; j = n - 1; while (i < j) { n = a[i] + a[j]; if (n == k) { printf("%d %d\n", a[i++], a[j--]); flag = true; } else if (n < k) { i++; } else { j--; } } if (!flag) { puts("No Solution"); } }