#UVa:10487-Closest Sums

灆洢 2016-08-02 08:06:10

將數字兩兩相加看看哪對離所求之數字最近即是解。

P.S. 其實最後搜尋部分可用二分搜尋加速,不過這題的數量小可以不用。

C++(0.010)

/*******************************************************/
/* UVa 10487 Closest Sums                              */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2016/08/02                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

int main(){
  int n;
  int testcase = 1;
  while( scanf("%d", &n) != EOF && n != 0 ){
    int num[1005];
    for( int i = 0 ; i < n ; ++i ){
      scanf("%d", &num[i]);
    }
    sort(num, num+n);

    int m;
    scanf("%d", &m);

    printf("Case %d:\n", testcase++);
    int query;
    for( int i = 0 ; i < m ; ++i ){
      scanf("%d", &query);

      int closetSum = num[0] + num[1];
      for( int j = 0 ; j < n ; ++j ){
        for( int k = j+1 ; k < n ; ++k ){
          int sum = num[j] + num[k];
          if( abs( sum - query ) < abs( closetSum - query ) ){
            closetSum = sum;
          }
          else if( sum - query > abs(closetSum - query) ){
            break;
          }
        }
      }

      printf("Closest sum to %d is %d.\n", query, closetSum);
    }


  }

  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料