BZOJ4240Gym102082G：贪心算法与树状数组的综合应用

Description

对家庭菜园有兴趣的JOI君每年在自家的田地中种植一种叫做IOI草的植物。JOI君的田地沿东西方向被划分为N个区域&＃xff0c;由西到东标号为1~N。IOI草一共有N株&＃xff0c;每个区域种植着一株。在第i个区域种植的IOI草&＃xff0c;在春天的时候高度会生长至hi&＃xff0c;此后便不再生长。

为了观察春天的样子而出行的JOI君注意到了IOI草的配置与预定的不太一样。IOI草是一种非常依靠阳光的植物&＃xff0c;如果某个区域的IOI草的东侧和西侧都有比它高的IOI草存在&＃xff0c;那么这株IOI草就会在夏天之前枯萎。换句话说&＃xff0c;为了不让任何一株IOI草枯萎&＃xff0c;需要满足以下条件&＃xff1a;

对于任意2<&＃61;i<&＃61;N-1&＃xff0c;以下两个条件至少满足一个&＃xff1a;

1. 对于任意1<&＃61;j<&＃61;i-1&＃xff0c;hj<&＃61;hi

2. 对于任意i&＃43;1<&＃61;j<&＃61;N&＃xff0c;hk<&＃61;hi

IOI草是非常昂贵的&＃xff0c;为了不让IOI草枯萎&＃xff0c;JOI君需要调换IOI草的顺序。IOI草非常非常的高大且纤细的植物&＃xff0c;因此JOI君每次只能交换相邻两株IOI草。也就是说&＃xff0c;JOI君每次需要选择一个整数i(1<&＃61;i<&＃61;N-1)&＃xff0c;然后交换第i株IOI草和第i&＃43;1株IOI草。随着夏天临近&＃xff0c;IOI草枯萎的可能性越来越大&＃xff0c;因此JOI君想知道让所有IOI草都不会枯萎的最少操作次数。

现在给出田地的区域数&＃xff0c;以及每株IOI草的高度&＃xff0c;请你求出让所有IOI草的不会枯萎的最少操作次数。

HINT

最终的高度序列为2 4 5 8 6 3&＃xff0c;共需要操作三次。

3<&＃61;N<&＃61;3*10^5

1<&＃61;hi<&＃61;10^9

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include //#pragma GCC optimize(2) using namespace std; #define maxn 300005 #define inf 0x7fffffff //#define INF 1e18 #define rdint(x) scanf("%d",&x) #define rdllt(x) scanf("%lld",&x) #define rdult(x) scanf("%lu",&x) #define rdlf(x) scanf("%lf",&x) #define rdstr(x) scanf("%s",x) #define mclr(x,a) memset((x),a,sizeof(x)) typedef long long ll; typedef unsigned long long ull; typedef unsigned int U; #define ms(x) memset((x),0,sizeof(x)) const long long int mod &＃61; 1e9 &＃43; 7; #define Mod 1000000000 #define sq(x) (x)*(x) #define eps 1e-5 typedef pair pii; #define pi acos(-1.0) //const int N &＃61; 1005; #define REP(i,n) for(int i&＃61;0;i<(n);i&＃43;&＃43;) typedef pair pii;inline int rd() {int x &＃61; 0;char c &＃61; getchar();bool f &＃61; false;while (!isdigit(c)) {if (c &＃61;&＃61; &＃39;-&＃39;) f &＃61; true;c &＃61; getchar();}while (isdigit(c)) {x &＃61; (x <<1) &＃43; (x <<3) &＃43; (c ^ 48);c &＃61; getchar();}return f ? -x : x; }ll gcd(ll a, ll b) {return b &＃61;&＃61; 0 ? a : gcd(b, a%b); } int sqr(int x) { return x * x; }/*ll ans; ll exgcd(ll a, ll b, ll &x, ll &y) {if (!b) {x &＃61; 1; y &＃61; 0; return a;}ans &＃61; exgcd(b, a%b, x, y);ll t &＃61; x; x &＃61; y; y &＃61; t - a / b * y;return ans; } */ll ans; int n, l, r; struct node {int v, p; }t[maxn]; int tr[maxn]; bool cmp(node a, node b) {return a.v > b.v; } void add(int x) {while (x <&＃61; n) {tr[x]&＃43;&＃43;; x &＃43;&＃61; x & -x;}}int query(int x) {int rs &＃61; 0;while (x > 0) {rs &＃43;&＃61; tr[x]; x -&＃61; x & -x;}return rs; }int main() {// ios::sync_with_stdio(0);n &＃61; rd();for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)t[i].v &＃61; rd(), t[i].p &＃61; i;sort(t &＃43; 1, t &＃43; 1 &＃43; n, cmp);for (int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) {int tp &＃61; i; while (t[tp].v &＃61;&＃61; t[tp &＃43; 1].v&&tp }