第一题，luogu原题。。。堆排序。。。二分也可。
第二题。。。。不会，瞎搞。。。直到提交前还在反复测数据。
维护一个单调递减的单调队列/单调栈 每次插入高度时 若队中已有高度低于这头牛的牛 就判断队中牛能向左延伸到的那头牛能否被这头牛延伸到 （特判高度相等的） 然后每个位置计算答案并更新。
维护一个Node的单调栈，Node各元素的含义为：
v，p：该Node代表的值（value）和其在序列中所在的位置（position）
mv，mp：对于所有以该元素为开头的合法序列，结尾的最大值及其所在位置
#define B cout << "BreakPoint" << endl;
#define O(x) cout << #x << " " << x << endl;
#define O_(x) cout << #x << " " << x << " ";
#define Msz(x) cout << "Sizeof " << #x << " " << sizeof(x)/1024/1024 << " MB" << endl;
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#define rep(id,a,b) for(int id = (a);id < (b);id++)
#define irep(id,a,b) for(int id = (a);id > (b);id--)
#define reset(arr,c) memset(arr,c,sizeof(arr))
#define N 100005
typedef long long int64;
using namespace std;
int n,h[N];
inline int read() {
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
void input() {
n = read();
rep (i, 0, n)
h[i] = read();
}
struct Node {
int v, p, mv, mp;
Node (int _v, int _p, int _mv, int _mp) :
v (_v), p (_p), mv (_mv), mp (_mp) {}
};
int solve() {
int ans = 0;
stack<Node> st;
irep (i, n - 1, -1) {
int m = h[i], p = i;
while (!st.empty() && h[i] < st.top().v) {
if (st.top().mv > m) {
m = st.top().mv;
p = st.top().mp;
}
st.pop();
}
st.push (Node (h[i], i, m, p) );
ans = max (ans, p - i + 1);
}
return (ans == 1) ? 0 : ans;
}
int main() {
input();
printf ("%d
", solve() );
return 0;
}
第三题：
可以进行二分，二分算法。
用前缀和将环一分为二，再枚举答案。
或者我们可以这样。
把这个圆顺时针做前缀和，然后枚举两边的值并比较即可。大概O（2n）。
下面是个O（n）算法，很妙。
可以把这个圆看作一条直线
设立一个l，一个r分别指向这条直线，l到r之间的距离为x
那么最右值肯定是越靠近总和除以2越好
1 2 3 4 5 … n
l r
那么，当x小于sum/2时，r往右靠，（一遍做一边打擂），如果x大于sum/2，那么l向右靠，当r到n时，循环结束，答案得出 。