NKOJ3485 【2015多校联训4】数据

问题描述

Mr_H 出了一道信息学竞赛题，就是给 n 个数排序。输入格式是这样的：
试题有若干组数据。每组数据的第一个是一个整数 n，表示总共有 n 个数待排序；接下来 n 个整数，分别表示这n 个待排序的数。
例如：3 4 2 –1 4 1 2 3 4，就表示有两组数据。第一组有3 个数(4,2,-1)，第二组有4个数(1,2,3,4)。可是现在Mr_H 做的输入数据出了一些问题。
例如：2 1 9 3 2 按理说第一组数据有2 个数(1,9)，第二组数据有3 个数，可是“3”后面并没有出现三个数，只出现了一个数“2”而已！
现在 Mr_H 需要对数据进行修改，改动中“一步”的含义是对文件中的某一个数+1 或-1，写个
程序，计算最少需要多少步才能将数据改得合法。

输入格式

第一行一个整数m，表示Mr_H 做的输入数据包含的整数个数。第二行包含m 个整数a[i]，每个整数的绝对值不超过10000。

输出格式

一个整数，表示把数据修改为合法的情况下，最少需要多少步。

样例输入

【样例输入1】
4
1 9 3 2

【样例输入2】
10
4 4 3 5 0 -4 -2 -1 3 5

样例输出

【样例输出1】
2

【样例输出2】
3

提示

【数据范围】
对于 20%的数据，m<=10, |a[i]|<=5;
对于60%的数据，m<=5000, |a[i]|<=10000
对于100%的数据，m<=100000, |a[i]|<=10000

来源 by YZ

【题解】

dp(i)=min{dp(j)+|num(j+1)-(i-j-1)|}

num(j+1)-(i-j-1)>=0 ，即i<num(j+1)+j+1时 dp(i)=min{dp(j)+num(j+1)+j+1}-i
num(j+1)-(i-j-1)<0，即i>num(j+1)+j+1时 dp(i)=min{dp(j)-num(j+1)-j-1}-i
我们不难用一颗权值线段树去维护，线段树的下标表示num(j+1)+j+1，值
为dp(j)-num(j+1)-j-1 / dp(j)+num(j+1)+j+1的最小值。

查询dp(j)+num(j+1)+j+1线段树的i....max和

dp(j)-num(j+1)-j-1线段树的1...i-1即可

对拍无误

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #define max(a, b) ((a) > (b) ? (a) : (b))

 #define min(a, b) ((a) < (b) ? (a) : (b))

 inline void read(int &x)

 {

     x = ;char ch = getchar(), c = ch;

     while(ch < '' || ch > '')c = ch, ch = getchar();

     while(ch <= '' && ch >= '')x = x *  + ch - '', ch = getchar();

     if(c == '-')x = -x;

 }

 const int MAXM =  + ;

 const int MAXNUM = ;

 const int PIAN = ;

 const int INF = 0x3f3f3f3f;

 int m,dp[MAXM],num[MAXM];

 int mi[][MAXNUM + ], sum;

 /*

 f(i)=min{f(j)+|A(j+1)-(i-j-1)|}

 0: num(j+1)-(i-j-1)>0 -> i<num(j+1)+j+1  f(i)=min{f(j) + num(j+1) - (-j-1)} - i

 1: num(j+1)-(i-j-1)<=0 -> i>num(j+1)+j+1 f(i)=min{f(j) + (-j-1) - num(j+1)} + i

 */

 void modify(int a, int p, int k, int o = , int l = , int r = sum + PIAN)

 {

     if(l == r && l == p)

     {

         mi[a][o] = min(k, mi[a][o]);

         return;

     }

     int mid = (l + r) >> ;

     if(mid >= p)modify(a, p, k, o << , l, mid);

     else modify(a, p, k, o <<  | , mid + , r);

     mi[a][o] = min(mi[a][o], min(mi[a][o << ], mi[a][o <<  | ]));

 }

 int ask(int a, int ll, int rr, int o = , int l = , int r = sum + PIAN)

 {

     if(ll <= l && rr >= r) return mi[a][o];

     int mid = (l + r) >> ;

     int ans = INF;

     if(mid >= ll)ans = min(ans, ask(a, ll, rr, o << , l, mid));

     if(mid < rr)ans = min(ans, ask(a, ll, rr, o <<  | , mid + , r));

     return ans;

 }

 int main()

 {

     read(m);

     for(register int i = ;i <= m;++ i)

         read(num[i]), sum = max(sum, num[i] + i +  + PIAN);

     memset(dp, 0x3f, sizeof(dp));

     memset(mi, 0x3f, sizeof(mi));

     dp[] = ;

     modify(,num[] +  + PIAN, num[] + );

     modify(,num[] +  + PIAN, -num[] - );

     for(register int i = ;i <= m;++ i)

     {

         int k1 = ask(, min(sum, i) + PIAN, sum + PIAN) - i;

         int k2 = ask(, , max(, i - ) + PIAN) + i;

         if(k2 <= i - INF)k2 = INF;

         dp[i] = min(dp[i], min(k1, k2));

         modify(, num[i + ] + i +  + PIAN, dp[i] + num[i + ] + i + );

         modify(, num[i + ] + i +  + PIAN, dp[i] - num[i + ] - i - );

     }

     printf("%d", dp[m]);

     return ;

 }

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstdlib>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int inf=0x3f3f3f3f;

 template <typename T>

 inline void _read(T& x){

     char t=getchar();bool sign=true;

     while(t<''||t>'')

     {if(t=='-')sign=false;t=getchar();}

     for(x=;t>=''&&t<='';t=getchar())x=x*+t-'';

     if(!sign)x=-x;

 }

 int n;

 int a[];

 int f[];

 int mark[];

 vector<int> v[];

 struct node{

     int x,y;

     node(){}

     node(int g,int h){x=g;y=h;}

     bool operator < (const node p)const {

         return y>p.y;

     }

 };

 priority_queue<node>q1;

 priority_queue<node>q2;

 void dajia(){

     int i,j,k;

     for(i=;i<=n;i++){

         f[i]=inf;

         for(k=i-;k>=;k--){

             f[i]=min(f[i],f[k]+abs(a[k+]-(i-k-)));

         }

     }

 }

 void daqunjia(){

     int i,j,k,temp;

     q1.push(node(,a[]+));

     for(i=;i<=n;i++){

         temp=-;

         for(j=;j<v[i].size();j++){

             mark[v[i][j]]=;

             if(v[i][j]<i)q2.push(node(v[i][j],f[v[i][j]]-a[v[i][j]+]-v[i][j]-));

         }

         while(q1.size()&&mark[q1.top().x]==){

             q1.pop();

         }

         if(q1.size()){

             temp=q1.top().y-i;

         }

         if(q2.size()){

             if(temp==-)temp=q2.top().y+i;

             else temp=min(temp,q2.top().y+i);

         }

         f[i]=temp;

         if(mark[i]==){

             q2.push(node(i,f[i]-a[i+]-i-));

         }

         else q1.push(node(i,f[i]+a[i+]+i+));

     }

 }

 int main(){

     freopen("data.txt", "r", stdin);

     int i,j,k,temp;

     cin>>n;

     for(i=;i<=n;i++){

         _read(a[i]);

         if(a[i]+i<=)v[].push_back(i-);

         v[a[i]+i].push_back(i-);

     }

     if(n<=)dajia();

     else daqunjia();

     cout<<f[n];

 }

std

 #include <bits/stdc++.h>

 const int MAXN = ;

 const int MAXNUM = ;

 int main()

 {

     srand(time(NULL));

     int n = rand() % MAXN + ;

     printf("%d\n", n);

     for(register int i = ;i <= n;++ i)

     {

         int b = rand()%;

         if(b) printf("%d ",-rand()%MAXNUM+);

         else printf("%d ", rand()%MAXNUM+);

     }

     return ;

 }

rand

巴特西