题解：CF599C Day at the Beach

题目传送门

题意

有

n

座城堡，编号为

1

到

n

，第

i

座城堡的高度为

h_i

。现在要将这些城堡重新排序，使得对于所有的

i

（从

1

到

n−1

），都满足：

h_i\le h_{i+1}

。
排序过程：

将城堡被分成若干个块，每块包含连续的城堡，一个块里可以只有一个城堡，每一个城堡都在某一个分块中。
每个块独立排序，使得 $h_i,h_{i+1},\dots,h_j$ 有序。
分块方式应保证所有的块内部排序后，整个序列 $h_i$ 也变得有序。

你的任务是确定满足上述要求最多可以将城堡分成多少个块。

思路

我们输入时，设原输入未排序的高度为一个数组

x

，排序完的高度视为数组

y

。我们可以枚举一遍数组的相邻的两项之差存入一个计算器里面累加，如果此计数器的最终结果为

0

那么就是有序的。最后用一个变量存储答案，结果直接输出答案就行。

注意事项

如果数组

x

，数组

y

相等，那么这个数组本来就是有序的。

code

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
ll h[maxn],nh[maxn],x,sum,ans,i,j,n,c;
signed main()
{
	scanf("%lld",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%lld",&x);
		nh[i]=h[i]=x;
	}
	sort(nh+1,nh+1+n);
	for(i=1;i<=n;i++)
	{
        c=h[i]-nh[i];
        if(sum+c==0)ans++;
        sum+=c;
	}
	cout<<ans<<endl;
	return 0;
}

题解：CF599C Day at the Beach

文章操作

题目传送门

题意

思路

注意事项

code

相关推荐

评论

题解：CF599C Day at the Beach