构造一个长度是n的正整数数组且保证 a1+a2+…+an 的值尽可能小
等于号 x[i] >= x[i-1]+0 且 x[i+1] >= x[i]+0
大于号 x[i] >= x[i+1]+1
小于号 x[i+1] >= x[i]+1
题目会给我们n-1个不等式,让我们求这个不等式组的可行解,且使n个数的和最小.
那么我们可以用差分约束来解决
a[i] 必须大于等于1,所以我们要使用超级源点
求最小值,即求最长路.
#include<iostream> //最小
#include<queue>
#include<string.h>
using namespace std;
const int N=1010,M=4e3;
int h[N], e[M], ne[M], w[M], idx;
int dist[N],st[N];
void add(int a,int b,int c){
e[idx]=b, w[idx]=c, ne[idx]=h[a], h[a]=idx++;
}
void spfa(){
memset(dist,-0x3f,sizeof dist);
dist[0]=0;
st[0]=1;
queue<int> q;
q.push(0);
while(q.size()){
auto t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]<dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if(st[j]==0){
st[j]=1;
q.push(j);
}
}
}
}
}
int main(){
int n;
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n-1;++i){
char c;
cin>>c;
if(c=='=') add(i,i+1,0),add(i+1,i,0);
else if(c=='<') add(i,i+1,1);
else add(i+1,i,1);
}
for(int i=1;i<=n;++i) add(0,i,1);
spfa();
for(int i=1;i<=n;++i) printf("%d ",dist[i]);
return 0;
}