Kobolds and Catacomb

NC230837. Kobolds and Catacomb

描述

Kobolds are rat-like, candle-loving cave folk, digging deep beneath the surface for millennia. Today, they gather together in a queue to explore yet another tunnel in their catacombs!

But just before the glorious movement initiates, they have to arrange themselves in non-descending heights. The shortest is always the leader digging small holes, and the followers swelling it.

The kobolds are hyperactive; they like to move here and there. To make the arrangement easier, they decide to group themselves into consecutive groups first, then reorder in each group.

What's the maximum number of consecutive groups they can be partitioned into, such that after reordering the kobolds in each group in non-descending order, the entire queue is non-descending?

For example, given a queue of kobolds of heights [1, 3, 2, 7, 4], we can group them into three consecutive groups ([1] [3, 2] [7, 4]), such that after reordering each group, the entire queue can be non-descending.

输入描述

The first line of the input contains a single integer  , denoting the number of kobolds.

The second line contains  integers  , representing the heights of the kobolds in the queue.

输出描述

Print a single integer, denoting the maximum number of groups.

示例1

输入:

5
1 3 2 7 4

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 469ms, 内存消耗: 8236K, 提交时间: 2021-11-24 10:08:25

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],mn=1e9,mx=0,b[N],ans;

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=n;i>=1;i--){
		b[i]=mn;
		mn=min(mn,a[i]);
	}
	for(int i=1;i<=n;i++){
		mx=max(mx,a[i]);
		if(mx<=b[i]) ans++;
	}
	cout<<ans<<"\n";
}

pypy3 解法, 执行用时: 1126ms, 内存消耗: 150412K, 提交时间: 2021-11-23 21:31:19

n = int(input())
a = list(map(int, input().split()))
b = [x for x in a]
sumA = 0
sumB = 0
b.sort()
cnt = 0
for i in range(n):
    sumA += a[i]
    sumB += b[i]
    if sumA == sumB:
        cnt += 1
print(cnt)

Python3 解法, 执行用时: 1520ms, 内存消耗: 123908K, 提交时间: 2021-11-20 20:27:57

n = int(input())
a = list(map(int,input().split()))
b = a[::]
s1 = 0; s2 = 0; b.sort()
ans = 0
for i in range(n):
    s1 += a[i]
    s2 += b[i]
    ans += 1 if s1 == s2 else 0
print(ans)