輸入一個遞增排序的數組和一個數字S，在數組中查找兩個數，是的他們的和正好是S，如果有多對數字的和等於S，輸出兩個數的乘積最小的。 輸入： 每個測試案例包括兩行： 第一行包含一個整數n和k，n表示數組中的元素個數，k表示兩數之和。其中1 <= n <= 10^6，k為int 第二行包含n個整數，每個數組均為int類型。 輸出： 對應每個測試案例，輸出兩個數，小的先輸出。如果找不到，則輸出“-1 -1” 樣例輸入： 6 15 1 2 4 7 11 15 樣例輸出： 4 11 思想：因為已經排好序，那麼如果存在那麼兩個數，可能是一個比較大，一個比較小，或者是比較相等的兩個數！所以我們設一個n1=min(即a[0])，n2=max( 即a[n-1] )開始，實際是n1 = a[low],low=0開始，n2 = a[high],high=n-1開始，然後n1+n2與S(我們需要的和)進行比較，若>，則n2 =a[--high]；若<, n1=a[++low]，若==，則使用mul保存乘積，還要保存兩個數，因為可能不只一對數，它只要乘積小的！掃描直到low>=high終止！ 代碼AC： [cpp] #include <stdio.h> #include <stdlib.h> int main() { long int n, i, low, high; long long int mul; long int s, *data, m1, m2, flag; while(scanf("%ld%ld", &n, &s) != EOF ) { data =( long int* )malloc( sizeof( long int ) * n ); for( i = 0; i < n; i++ ) // { scanf("%ld", &data[i]); } m1 = -1; m2 = -1; low = 0; high = n - 1; mul = -1; flag = 1; while( low < high ) // 注意：負數和重復的數字( 可以無視 ) { if( data[low] + data[high] > s ) { high--; } else if( data[low] + data[high] < s ) { low++; } else { if( flag ) { mul = data[low] * data[high]; m1 = data[low]; m2 = data[high]; flag = 0; } else { if( mul > data[high] * data[low] ) { mul = data[high] * data[low]; m1 = data[low]; m2 = data[high]; } } // printf("%d %d\n", data[low], data[high]); low++; high--; } } printf("%ld %ld\n", m1, m2); free( data ); } return 0; }
