1901: 赏赐 OR 灾难

赏赐 OR 灾难"/>

1901: 赏赐 OR 灾难

1901: 赏赐 OR 灾难

      Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 418     Solved: 110    

---

Description

大G南征北战终于打下了大片土地成立了G国，大G在开国大典上传召帮助自己南征北战的三大开国元勋小A，小B，小C进殿，并要赏赐三人大量宝物以显示天恩浩荡。大G在征服其他国家的时候抢夺了n箱宝物，他把这些箱子依次排列在三人面前，每个箱子里的宝物都有一个价值wi，大G令他们一人选取一个箱子作为奖励。可是令大G万万没有想到的是，三人在私底下是存在竞争关系的，由于小B手上兵权强于小C，小C手上兵权强于小A。所以弱者总是担心自己领取的赏赐高于或等于强者会招来杀身之祸。所以他们三人总是会让小B先选取奖励之后，小C会在小B选择的右侧区域选择价值比小B小的奖励,而小A则会在小B选择的左侧区域选择价值比小B和小C都小的奖励。当然小B是个聪明人，他也会考虑到两人的想法选择对大家都有帮助的方案选取。请问是否存在这样一种选择方案让大家都不用担心会招致杀身之祸。如果存在输出“YES”，否则输出“NO”

Input

多组数据读入
每组数据第一行输入一个正整数n表示n箱宝物（n<=100000）接下来一行输入n个正整数w₁,w₂,w₃,...,w_n表示n箱宝物的价值。(w_i<=10000000)题目保证所有数据n的总和不超过500000

Output

如果存要求的选择方案则输出“YES”，否则输出“NO”。

Sample Input

6
1 2 3 6 5 4
6
1 2 3 4 5 6

Sample Output

YES
NO

思路：预处理求得B所选宝物左边的最小值，栈求的B所选宝物右边的最大值。B所选的宝物从右往左扫描，一旦有符合条件的就跳出。

#include<iostream>
#include<stack>
using namespace std;
int a[100005],m[100005];
int main()
{int n;stack<int> s;while (scanf ("%d",&n)==1){while (!s.empty())s.pop();//清空栈for (int i = 0;i < n;i++){scanf ("%d",&a[i]);if(i)//记录前i项的最小值{m[i]=min(m[i-1],a[i]);}else{m[0] = a[0];}}s.push(a[n-1]);//将最后一个元素入栈，栈内元素是将军C可选的奖励bool f=false;for (int i = n-2;i >0;i--)//从后往前进行扫描，寻找满足条件的{int A=m[i-1];//将军A选择前i-1项中最小的，B选第i项int c=-1;//初始化C的选择while (!s.empty() && s.top() < a[i])//若栈非空并且栈顶小于a[i]，说明栈顶可以给C{if(s.top()>c)//保证C取得的是i后面最大的一个c=s.top();s.pop();//此元素已经被C取得，故须删除}s.push(a[i]);//确保栈非空，为下次循环做准备if(A < c)//a<c则说明如此分配是满足条件的，可以跳出了{cout << "YES\n";f=true;break;}}if(!f)cout << "NO\n";}return 0;
}