SRM691 D2E PlusoneGame

TopCoder Statistics - Problem Statement

Hero plays a game with a deck of cards and a counter. Initially, the counter is set to zero. During the game Hero must play each card in the deck exactly once. He gets to choose the order in which he plays the cards. You are given the description of the deck in the String s.

文字列 が与えられる． の場合はカウンターをインクリメント， の場合は現在のカウンターとその桁の数の差の絶対値分，ペナルティがたまる．ペナルティが最小にように文字列を並び替えたい．

各桁を引く前にカウンターがその数と同じだけたまっている状態になっていれば，ペナルティは となる． なので，があるだけのように交互に並べ，足りない場合は 無しで，余った場合は最後につけた．

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

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

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
typedef long long ll;

class Plusonegame {
  public:
  string getorder(string s) {
      int n = s.size();
      map<char, int> m;
      int cnt = 0;

      rep(i, n) {
          if(s[i] == '+') cnt++;
          else {
              m[s[i]]++;
          }
      }

      string ans = "";
      rep(i, 10) {
          char c = '0' + i;

          rep(j, m[c]) {
              ans += c;
          }

          if(cnt > 0) {
              ans += '+';
              cnt--;
          }
      }

      while(cnt) {
          ans += '+';
          cnt--;
      }

      return ans;
  }
};
May 31st, 2016
srm, topcoder