Codeforces Round #101 (Div. 2) C - Queue

http://codeforces.com/contest/141/problem/C

概要

n 人の人が各々「自分より前に自分より背の高い人は a[i] 人いる」という情報を覚えている．

a[0], ..., a[n-1] が与えられたとき，矛盾無く一列に並べることができるかどうか答える． 矛盾無く一列に並べることができる場合，先頭の人から順に身長 h[i] の具体例も答える．

制約

• 1 <= n <= 3000
• 0 <= a[i] <= n-1
• 1 <= h[i] <= 10^9

解法

a を昇順にソートし，a[i] > i となる i が存在するときは NO．

そうでないときは，先頭から h[i] = i-a[i] を割り当てる． このとき，それに応じて i より前の人の割り当てをインクリメントして帳尻を合わせる．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   ios::sync_with_stdio(false);
 9   int N;
10   cin >> N;
11   vector<pair<int,string> > v(N);
12   for (int i = 0; i < N; i++) {
13     cin >> v[i].second >> v[i].first;
14   }
15   sort(v.begin(), v.end());
16   vector<int> ans(N, 0);
17   for (int i = 0; i < N; i++) {
18     const int a = v[i].first;
19     int r = i-a;
20     if (r < 0) {
21       cout << -1 << endl;
22       return 0;
23     }
24     for (int j = 0; j < i; j++) {
25       if (ans[j] >= r) {
26         ++ans[j];
27       }
28     }
29     ans[i] = r;
30   }
31   for (int i = 0; i < N; i++) {
32     cout << v[i].second << ' ' << ans[i]+1 << endl;
33   }
34   return 0;
35 }