打卡信奥刷题（2990）用C++实现信奥题 P6099 [USACO19FEB] Dishwashing G

P6099 [USACO19FEB] Dishwashing G题目背景Bessie 和 Elsie 正在帮助 Farmer John 洗碗这是一个比人们想象的更复杂的过程。题目描述两头奶牛决定 Bessie 负责涂肥皂Elsie 负责冲洗。刚开始的时候NNN个脏盘子保证是从111到NNN的一个排列堆在 Bessie 那里而 Elsie 这边的堆是空的。而在她们俩之间则有一张专门放涂过肥皂的盘子的桌子。每个冲洗步骤需要执行以下两个操作之一Bessie 从脏盘子堆顶取出一个盘子涂上肥皂然后放在桌子上。将这个盘子放在桌子上时Bessie 只能放在现有的非空盘堆的顶端或是在最右边新增一个盘堆。Elsie 从桌子最左边的盘堆的顶端拿起盘子将它冲洗后放在干净的盘堆顶端。她们希望干净的盘堆能按编号排序编号最小的在底端编号最大的在顶端。然而她们发现有的时候这并不可能做到。现在给定脏盘子的堆叠顺序请你求出一个最大前缀使得该前缀的所有盘子洗干净后能按上面的要求堆叠。输入格式第一行一个整数NNN1≤N≤1051 \leq N \leq 10^51≤N≤105。接下来NNN行每行一个整数代表 Bessie 的脏盘子堆的堆叠顺序。输入的第一个盘子在堆的顶部。输出格式输出该序列的最大前缀长度使得该前缀的所有盘子洗干净后能按小号在下大号在上的规则堆叠。输入输出样例 #1输入 #15 4 5 2 3 1输出 #14C实现#includebits/stdc.husingnamespacestd;intn,placed,base[100001];vectorintitem[100001];intmain(){cinn;for(inti1;in;i){intx;cinx;if(xplaced){couti-1;return0;}for(intjx;j0!base[j];j--)base[j]x;while(!item[base[x]].empty()item[base[x]].back()x){placeditem[base[x]].back();item[base[x]].pop_back();}item[base[x]].push_back(x);}coutn;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容