Codeforces352-div2D Robin Hood

Problem - D - Codeforces

We all know the impressive story of Robin Hood. Robin Hood uses his archery skills and his wits to steal the money from rich, and return it to the poor. There are n citizens in Kekoland, each person has coins.

　人いて，コインを 枚持っている． 回，ある人からコインを取って，ある人に挙げれる時，商人のコインの最大値と最小値の差を最小化する．

全員が持つコインの枚数を分探索．最大値と最小値の差を最大化したいので，最大値の最小化と，最小値の最大化を取って差を取る．コインの枚数を と決めた時に， より(多い / 少ない)コインの枚数が 枚以下かどうかが条件となる．
全てのコインの合計が人で割り切れない時は，必ず余りが出るので，その差 が答えになる．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, k;
  cin >> n >> k;

  vector<ll> v(n);
  ll lv = INF, rv = 0;
  ll sum = 0;
  rep(i, n) {
      cin >> v[i];
      sum += v[i];
      lv = min(lv, v[i] - 1);
      rv = max(rv, v[i] + 1);
  }

  sort(v.begin(), v.end());

  ll l = lv, r = rv;
  ll vmax = 0, vmin = INF;
  while(r - l > 1) {
      ll mid = (l + r) / 2;
      ll cnt = 0;
      rep(i, n) {
          if(v[i] > mid) {
              cnt += v[i] - mid;
          }
      }

      if(cnt <= k) {
          vmin = min(vmin, mid);
          r = mid;
      } else {
          l = mid;
      }
  }

  l = lv, r = rv;
  while(r - l > 1) {
      ll mid = (l + r) / 2;
      ll cnt = 0;
      rep(i, n) {
          if(v[i] < mid) {
              cnt += mid - v[i];
          }
      }

      if(cnt <= k) {
          vmax = max(vmax, mid);
          l = mid;
      } else {
          r = mid;
      }
  }

  if(sum % n == 0) {
      cout << max(0LL, vmin - vmax) << endl;
  } else {
      cout << max(1LL, vmin - vmax) << endl;
  }

  return 0;
}
May 12th, 2016
2分探索, codeforces