网络推广 SEO优化 网站建设,wordpress优化0sql,怎么自己做个免费网站,酒楼网站模板正题
nowcoder 11253-K 题目大意
有n个数#xff0c;依次加进栈中#xff0c;每次加入前将栈顶比aia_iai大的所有元素弹掉#xff0c;加入后记bib_ibi为栈的大小
现在给你b中的一些数#xff0c;让你求a数组的一种合法方案#xff0c;其中1~n在a中各出现了一次 解题…正题
nowcoder 11253-K 题目大意
有n个数依次加进栈中每次加入前将栈顶比aia_iai大的所有元素弹掉加入后记bib_ibi为栈的大小
现在给你b中的一些数让你求a数组的一种合法方案其中1~n在a中各出现了一次 解题思路
每次把栈顶比aia_iai大的所有元素弹掉使得栈是单调递增的
对于所求a数组可以先连边表示该点要比哪个点大然后跑拓扑序
那么可以遍历每个b如果当前栈中剩余的数大于了bib_ibi个那么把这些数弹掉且弹掉的数中最小的数连向i这些数要比aia_iai大才能被弹掉把i加进栈中然后连向栈顶栈顶不会被弹掉
最后跑拓扑序编号 代码
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 1000100
using namespace std;
int n, m, x, w, p, g, res, st[N], v[N], b[N], to[N], deg[N];
queueintd;
void bfs()
{for (int i 1; i n; i)if (!deg[i]) d.push(i);w n;while(!d.empty()){int u d.front();d.pop();v[u] w--;if (!--deg[to[u]]) d.push(to[u]);}return;
}
int main()
{scanf(%d%d, n, m);for (int i 1; i m; i){scanf(%d, x);scanf(%d, b[x]);}res 0;for (int i 1; i n; i){if (b[i]){if (b[i] res 1)//所要求的比当前剩余的大所以不可能{p 1;break;}g 0;while(b[i] res 1)//多了res--, g 1;if (g) to[st[res 1]] i;//最低的点比大}st[res] i; //入栈to[st[res]] st[res - 1];//i比栈顶大}if (p 1){puts(-1);return 0;}for (int i 1; i n; i)deg[to[i]];bfs();//跑拓扑序for (int i 1; i n; i)printf(%d , v[i]);return 0;
}
