列表

详情

NC53255. 有趣的家庭菜园

描述

题目译自 JOISC 2014 Day1 T2「たのしい家庭菜園」
JOI君对家庭菜园感兴趣。他每年在自家的田地中种植一种叫做IOI草的植物。JOI君的田地沿东西方向被划分为N个区域，由西到东标号为。IOI草一共有N株，每个区域种植着一株。在第i个区域种植的IOI草，在春天的时候高度会生长至h_i，此后便不再生长。
去踏青的JOI君注意到，IOI草的配置与预定的不太一样。IOI草是一种非常依靠阳光的植物，如果某个区域的IOI草的东侧和西侧都有比它高的IOI草存在，那么这株IOI草就会在夏天之前枯萎。换句话说，为了不让任何一株IOI草枯萎，，以下两个条件至少满足一个：
  • ；
  • 。
IOI草非常昂贵，为了不让IOI草枯萎，JOI君需要调换IOI草的顺序。IOI草是一种非常高大且纤细的植物，因此JOI君每次只能交换相邻两株IOI草。也就是说，JOI君每次需要选择一个整数i，然后交换第i株IOI草和第i+1株IOI草。随着夏天临近，IOI草枯萎的可能性越来越大，因此JOI君想让所有IOI草都不枯萎。
现在给出田地的区域数，以及每株IOI草的高度，请你求出让所有IOI草的不会枯萎的最少操作次数。

输入描述

第一行一个正整数N，代表田地被分为了N个区域。
接下来N行，第i行一个整数h_i，表示第i株植物在春天时的高度。

输出描述

输出一行一个整数，表示最少需要的操作次数。

示例1

输入: 

6
2
8
4
5
3
6

输出: 

3

说明:

初始情况：
JOISC.2014.D1T2.1.png
操作方式：

示例2

输入: 

5
4
4
2
4
4

输出: 

2

说明:

将第3株IOI草移动到区域1或区域5。

示例3

输入: 

4
1
3
4
2

输出: 

0

原站题解

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

C++11(clang++ 3.9) 解法, 执行用时: 117ms, 内存消耗: 3888K, 提交时间: 2020-08-11 21:30:39 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=300010;
int n;
struct node{int h,id;}a[maxn];
bool cmp(node x,node y){return x.h>y.h;}
int s[maxn];
void add(int x,int y){for(int i=x;i<=n;i+=(i&-i))s[i]+=y;}
int getsum(int x){int re=0;for(int i=x;i;i-=(i&-i))re+=s[i];return re;}
int main()
{
    LL ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].h);
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    a[0].h=-1;
// for(int i=1;i<=n;i++)
// printf("%d %d %d\n",i,a[i].h,a[i].id);
    int ii=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i].h!=a[i-1].h){while(ii<i)add(a[ii++].id,1);}
        int t=getsum(a[i].id);
        ans+=(LL)(min(ii-1-t,t));
    }
    printf("%lld",ans);
}

上一题

© 2025 nowcoder.com