AcWing 4715. 构造数组(差分约束)

题目链接

AcWing 4715. 构造数组

请你构造一个长度为 n 的正整数数组 a1,a2,…,an。

我们会给出一个长度为 n−1 的由 <、>、= 组成的字符串 s1s2…sn−1 用于约束你的构造：

如果 si 为 <，则表示你构造的数组需满足 ai<ai+1。
如果 si 为 >，则表示你构造的数组需满足 ai>ai+1。
如果 si 为 =，则表示你构造的数组需满足 ai=ai+1。
你构造的正整数数组需满足上述约束的同时，保证 a1+a2+…+an 的值尽可能小。

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

输入格式
第一行包含整数 n。

第二行包含字符串 s1s2…sn−1。

输出格式
共一行，输出 a1,a2,…,an。

数据范围
前 3 个测试点满足 2≤n≤6。
所有测试点满足 2≤n≤1000。

输入样例1：
5

<><
输出样例1：
2 1 2 1 2
输入样例2：
5
=<<<
输出样例2：
1 1 2 3 4

题解：
① 若s[i] == ‘<’ 可以看作 a[i + 1] < a[i + 2] 即: a[i + 2] >= a[i + 1] + 1
② 若s[i] == ‘>’ 可以看作 a[i + 1] > a[i + 2] 即: a[i + 1] >= a[i + 2] + 1
③ 若s[i] == ‘=’ 可以看作 a[i + 1] = a[i + 2] 即: a[i + 1] >= a[i + 2] ,a[i + 2] >= a[i + 1]

题目中求最小值，则构造最长路。

（最小值构造最长路，最大值构造最短路）

#include<iostream>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int n;

const int N = 1100;

int a[N];
int h[N],e[N * 3],ne[N * 3],w[N * 3],idx;
int di[N],st[N];

void add(int u,int v,int w1)
{
	e[idx] = v,w[idx] = w1,ne[idx] = h[u],h[u] = idx ++;
}

void dist()
{
	queue<int>qu;
	memset(di,-0x3f3f,sizeof di);
	
	di[0] = 0;
	
	st[0] = true;
	
	qu.push(0);
	
	while(qu.size())
	{
		int t = qu.front();
		qu.pop();
		st[t] = false;
		for(int i = h[t];i != -1;i = ne[i])
		{
			int j = e[i];
			if(di[j] < di[t] + w[i])
			{
				di[j] = di[t] + w[i];
//				cout << j << ' ' << di[j] << endl;
				
				if(!st[j]) 
				{
					qu.push(j);
					st[j] = true;
				}
			}
		}
	}
}

int main()
{
	memset(h,-1,sizeof h);
	cin >> n;
	string s;
	cin >> s;
	for(int i = 0;i < n - 1;i ++)
	{
		if(s[i] == '=') add(i + 1,i + 2,0),add(i + 2,i + 1,0);
		else if(s[i] == '<') add(i + 1,i + 2,1);
		else add(i + 2,i + 1,1);
	}
	
	for(int i = 1;i <= n;i ++) add(0,i,1);
	
	dist();
	
	int ans = 0;
	
	for(int i = 1;i <= n;i ++)  cout << di[i] << ' ' ;
	
	cout << endl;
	return 0;
}