构造数组

请你构造一个长度为 $n$ 的正整数数组 $a_1,a_2, \ldots ,a_n$。

我们会给出一个长度为 $n−1$ 的由 $<$、$>$、$=$ 组成的字符串 $s_1s_2 \ldots s_{n−1}$ 用于约束你的构造：

• 如果 $s_i$ 为 $<$，则表示你构造的数组需满足 $a_i < a_{i+1}$。
• 如果 $s_i$ 为 $>$，则表示你构造的数组需满足 $a_i > a_{i+1}$。
• 如果 $s_i$ 为 $=$，则表示你构造的数组需满足 $a_i = a_{i+1}$。

你构造的正整数数组需满足上述约束的同时，保证 $a_1+a_2+ \ldots +a_n$ 的值尽可能小。

请你输出满足条件的正整数数组。数据保证一定有解。

输入格式

第一行包含整数 $n$。

第二行包含字符串 $s_1s_2 \ldots s_{n−1}$。

输出格式

共一行，输出 $a_1,a_2, \ldots ,a_n$。

数据范围

前 $3$ 个测试点满足 $2 \leq n \leq 6$。
所有测试点满足 $2 \leq n \leq 1000$。

输入样例1：

5
><><

输出样例1：

2 1 2 1 2

输入样例2：

5
=<<<

输出样例2：

1 1 2 3 4

解题思路

　　这是一道很经典的差分约束题，不过因为我不怎么熟悉所以比赛时没写出来。

　　因为要求最小值，所以应该是建图跑最长路。为什么是求最长路呢，这是因为求最短路时有三角不等式，例如如果有$a \to b$，那么求完最短路就会有$d_b \leq d_a + w_{ab}$。因此求最长路的话只需要把不等符号反过来，就会得到$d_b \geq d_a + w_{ab}$。因此我们只要把原问题给的约束条件都转换为$a \geq b + c$这种形式，然后建图（$b$到$a$连一条边，权值为$c$），跑最长路就可以了。

• $a = b \Longleftrightarrow a \geq b + 0 \, \And \, b \geq a + 0$。
• $a > b \Longleftrightarrow a \geq b + 1$。
• $a < b \Longleftrightarrow b \geq a + 1$。

　　另外，又因为每一个数都满足$a > 0$，等价于$a \geq 0 + 1$，因此我们可以规定$0$号点为超级原点，$d_0 = 0$。最后还需要建从$0$到所有点的权值为$1$的边。

　　AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1010, M = N * 3;
 5 
 6 int head[N], e[M], wts[M], ne[M], idx;
 7 int dist[N];
 8 int vis[N];
 9 
10 void add(int v, int w, int wt) {
11     e[idx] = w, wts[idx] = wt, ne[idx] = head[v], head[v] = idx++;
12 }
13 
14 void spfa() {
15     queue<int> q({0});
16     while (!q.empty()) {
17         int t = q.front();
18         q.pop();
19         vis[t] = false;
20         
21         for (int i = head[t]; i != -1; i = ne[i]) {
22             if (dist[e[i]] < dist[t] + wts[i]) {
23                 dist[e[i]] = dist[t] + wts[i];
24                 if (!vis[e[i]]) q.push(e[i]), vis[e[i]] = true;
25             }
26         }
27     }
28 }
29 
30 int main() {
31     int n;
32     cin >> n;
33     memset(head, -1, sizeof(head));
34     for (int i = 1; i < n; i++) {
35         char c;
36         cin >> c;
37         if (c == '>') add(i + 1, i, 1);         // a > b <-> a >= b + 1
38         else if (c == '<') add(i, i + 1, 1);    // a < b <-> b >= a + 1
39         else add(i, i + 1, 0), add(i + 1, i, 0);// a = b <-> a >= b + 0 and b >= a + 0
40     }
41     for (int i = 1; i <= n; i++) {  // a > 0 <-> a >= 0 + 1
42         add(0, i, 1);
43     }
44     
45     spfa();
46     
47     for (int i = 1; i <= n; i++) {
48         cout << dist[i] << ' ';
49     }
50     
51     return 0;
52 }

参考资料

　　AcWing 4715. 构造数组（AcWing杯 - 周赛）：https://www.acwing.com/video/4525/