CFR 351 A. Jeff and Rounding ( Ad hoc, Math )

kmjp さんの記事を参考にしました。
Problem - A - Codeforces

題意：
給你 2 * N 個數字，要把 N 個數向下取整，另外 N 個數向上取整。問總和的最小變化量是多少。

資料規模：
The first line contains integer n (1 ≤ n ≤ 2000). The next line contains 2n real numbers a1, a2, ..., a2n (0 ≤ ai ≤ 10000), given with exactly three digits after the decimal point. The numbers are separated by spaces.
TL: 1000 ms
ML: 256 MB

解法：
顯然輸入的整數部分沒有意義。砍掉整數部分後，乘以 1000 提升為整數問題，方便寫代碼。
若一個數 A[ i ] 向下取整，那麼對總變化的貢獻為 A[ i ] - floor( A[ i ] )。
若一個數 A[ i ] 向上取整，那麼對總變化的貢獻為 A[ i ] - ceil( A[ i ] )，而若 A[ i ] == 0，則等價 A[ i ] - floor( A[ i ] )，否則等價 A[ i ] - ( 1 + floor( A[ i ] )。可以觀察到，會左右總變化量的，只有「向上取整的數有多少個是整數」這件事情而已。因此暴力枚舉就可以。

時間 / 空間複雜度：
O( N )

int N;
vi A;

void init(){
  cin >> N;
  A = vi( 2 * N );
  for( int i = 0; i < 2 * N; ++i ){
    string s; cin >> s;
    for( int j = 0; j < s.size(); ++j ){
      s[ j ] -= '0';
    }
    A[ i ] = s[ s.size() - 3 ] * 100 + s[ s.size() - 2 ] * 10 + s[ s.size() - 1 ];
  }
}

void solve(){
  int ans = INF;
  int tot = 0;
  int nz_cnt = 0;
  for( int i = 0; i < 2 * N; ++i ){
    tot += A[ i ];
    nz_cnt += A[ i ] != 0;
  }
  for( int i = max( 0, nz_cnt - N ); i <= min( N, nz_cnt ); ++i ){
    upmin( ans, abs( tot - i * 1000 ) );
  }
  cout << ans / 1000 << "." << ans / 100 % 10 << ans / 10 % 10 << ans % 10 << endl;
}