一, 题解方法
维护一个单调递减队列, 如果输入元素大于队尾元素, 则清空队列. 因此, 队尾减队头就是所有矮于当前身高的奶牛数.
二, 题解代码
- #include <iostream>
- using namespace std;
- int que[80000];
- int head = 0, rear = -1;
- int main()
- {
- int n, input;
- long long ans = 0;
- cin>> n;
- while(n--){
- cin>> input;
while(rear>= head && input>= que[rear]) rear--; // 清除矮的
que[++rear] = input; // 插入
ans += rear - head; // 统计
- }
- cout << ans << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2552475.html