题解：CF599C Day at the Beach

zym20249_ · 2024-12-30 21:23:36 · 题解

题目传送门

题意

有 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

#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;
}