1244：和為給定數(shù)

時間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 8206 ??? 通過數(shù): 3053

【題目描述】

給出若干個整數(shù)，詢問其中是否有一對數(shù)的和等于給定的數(shù)。

【輸入】

第一行是整數(shù)n(0 < n ≤ 100,000)，表示有n個整數(shù)。

第二行是n個整數(shù)。整數(shù)的范圍是在0到10^8之間。

第三行是一個整數(shù)m（0≤m≤2^30)，表示需要得到的和。

【輸出】

若存在和為m的數(shù)對，輸出兩個整數(shù)，小的在前，大的在后，中間用單個空格隔開。若有多個數(shù)對滿足條件，選擇數(shù)對中較小的數(shù)更小的。若找不到符合要求的數(shù)對，輸出一行No。

【輸入樣例】

4 2 5 1 4 6

【輸出樣例】

1 5

【分析】

? ? ? ? 這道題本身并不難，首先看題目，題目說：若存在和為m的數(shù)對，輸出兩個整數(shù)，小的在前，大的在后，中間用單個空格隔開。若有多個數(shù)對滿足條件，選擇數(shù)對中較小的數(shù)更小的。很好想到兩個整數(shù)，小在前，大在后，如果我們排好序，就很容易實(shí)現(xiàn)這一點(diǎn)。其次，我們想到線性查找（枚舉），i 指向第一個數(shù)，j 指向 i+1，然后一次查找a[i]+a[j]==m。很可惜，從數(shù)據(jù)規(guī)模上看，枚舉必定超時。

【參考代碼1】枚舉超時版

#include <stdio.h> #include <stdlib.h> #define N 100010 int a[N]; int cmp(const void*a,const void*b) {return *(int*)a-*(int*)b; } int main() {int i,j,m,n;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&a[i]);scanf("%d",&m);qsort(a,n,sizeof(int),cmp);for(i=0;i<n-1;i++){for(j=i+1;j<n;j++){if(a[i]+a[j]==m){printf("%d %d\n",a[i],a[j]);return 0;}}}printf("No\n");return 0; }

? ? ? ? 查找的方法有兩種，一種是線性查找（枚舉），另一種則是折半查找（分治）。

【參考代碼2】

#include <stdio.h> #include <stdlib.h> #define N 100010 int a[N]; int cmp(const void*a,const void*b) {return *(int*)a-*(int*)b; } int main() {int i,j,m,n;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&a[i]);scanf("%d",&m);qsort(a,n,sizeof(int),cmp);i=0;j=n-1;while(i<=j){if(a[i]+a[j]>m)j--;else if(a[i]+a[j]<m)i++;else{printf("%d %d\n",a[i],a[j]);return 0;}}printf("No\n");return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1244

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（1244：和为给定数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。