SRM563 Div1 Easy

300

view plainprint?

1. class FoxAndHandle {  
2. public:  
3.   string lexSmallestName(string S)  
4.   {  
5.     string H;  
6.   
7.     const int N = S.size();  
8.     bool vis[N];  
9.     fill(vis, vis + N, false);  
10.   
11.     vector< pair<char, int> > cand;  
12.     for (int i = 0; i < N; ++i) {  
13.       cand.push_back(make_pair(S[i], i));  
14.     }  
15.     sort(cand.begin(), cand.end());  
16.   
17.     int prev = -1;  
18.     while (H.size() < S.size() / 2) {  
19.       for (int i = 0; i < cand.size(); ++i) {  
20.         int j = cand[i].second;  
21.         unless (prev < j) continue;  
22.         map<char, int> cnt;  
23.         for (int k = 0; k < N; ++k) {  
24.           ++cnt[S[k]];  
25.         }  
26.         for (int k = 0; k < H.size(); ++k) {  
27.           --cnt[H[k]];  
28.           --cnt[H[k]];  
29.         }  
30.         if (cnt[cand[i].first] <= 0) continue;  
31.   
32.         int rest = 0;  
33.         for (int k = j; k < N; ++k) {  
34.           if (2 <= cnt[S[k]]) {  
35.             ++rest;  
36.             cnt[S[k]] -= 2;  
37.           }  
38.         }  
39.         if (S.size() / 2 <= H.size() + rest) {  
40.           prev = j;  
41.           H += S[j];  
42.           vis[j] = true;  
43.           break;  
44.         }  
45.       }  
46.     }  
47.   
48.     return H;  
49.   }  
50. };  

class FoxAndHandle {
public:
  string lexSmallestName(string S)
  {
    string H;

    const int N = S.size();
    bool vis[N];
    fill(vis, vis + N, false);

    vector< pair<char, int> > cand;
    for (int i = 0; i < N; ++i) {
      cand.push_back(make_pair(S[i], i));
    }
    sort(cand.begin(), cand.end());

    int prev = -1;
    while (H.size() < S.size() / 2) {
      for (int i = 0; i < cand.size(); ++i) {
        int j = cand[i].second;
        unless (prev < j) continue;
        map<char, int> cnt;
        for (int k = 0; k < N; ++k) {
          ++cnt[S[k]];
        }
        for (int k = 0; k < H.size(); ++k) {
          --cnt[H[k]];
          --cnt[H[k]];
        }
        if (cnt[cand[i].first] <= 0) continue;

        int rest = 0;
        for (int k = j; k < N; ++k) {
          if (2 <= cnt[S[k]]) {
            ++rest;
            cnt[S[k]] -= 2;
          }
        }
        if (S.size() / 2 <= H.size() + rest) {
          prev = j;
          H += S[j];
          vis[j] = true;
          break;
        }
      }
    }

    return H;
  }
};