P5200 [USACO19JAN]Sleepy Cow Sorting

题目描述

Farmer John正在尝试将他的N头奶牛(1≤N≤10^5),方便起见编号为1…N,在她们前往牧草地吃早餐之前排好顺序。 当前,这些奶牛以p1,p2,p3,…,pN的顺序排成一行,Farmer John站在奶牛p1前面。他想要重新排列这些奶牛,使得她们的顺序变为1,2,3,…,N,奶牛1在Farmer John旁边。

今天奶牛们有些困倦,所以任何时刻都只有直接面向Farmer John的奶牛会注意听Farmer John的指令。每一次他可以命令这头奶牛沿着队伍向后移动k步,k可以是1到N−1之间的任意数。她经过的k头奶牛会向前移动,腾出空间使得她能够插入到队伍中这些奶牛之后的位置。

例如,假设N=4,奶牛们开始时是这样的顺序:

FJ: 4, 3, 2, 1 唯一注意FJ指令的奶牛是奶牛4。当他命令她向队伍后移动2步之后,队伍的顺序会变成:

FJ: 3, 2, 4, 1 现在唯一注意FJ指令的奶牛是奶牛3,所以第二次他可以给奶牛3下命令,如此进行直到奶牛们排好了顺序。

Farmer John急欲完成排序,这样他就可以回到他的农舍里享用他自己的早餐了。请帮助他求出一个操作序列,使得能够用最少的操作次数将奶牛们排好顺序。

输入格式

输入的第一行包含N。第二行包含N个空格分隔的整数:p1,p2,p3,…,pN,表示奶牛们的起始顺序。

输出格式

输出的第一行包含一个整数,K,为将奶牛们排好顺序所需的最小操作次数。 第二行包含K个空格分隔的整数,c1,c2,…,cK,每个数均在1…N−1之间。如果第i次操作FJ命令面向他的奶牛向队伍后移动ci步,那么K次操作过后奶牛们应该排好了顺序。

如果存在多种最优的操作序列,你的程序可以输出其中任何一种。

输入输出样例

输入 #1
4
1 2 4 3
输出 #1
3
2 2 3


分析

这题其实不难……感谢机房大佬分析orz

可依据插入排序的思想,已知对于一个长度为n的序列,最多移动n次可做到由小到大排序。而对于一个上升的序列,很显然是不必要进行排序的,所以实际的最小移动次数可以更小。根据这一发现,可模拟题中的情况进行分析。

对于1 2 4 3的情况,依据上面的想法,更改情况为:1 2 4 3——2 4 3 1——4 3 1 2——3 1 2 4——1 2 3 4,即进行了4次修改,而正确答案是3次。为什么呢?比对输出的数据,我们发现序列中的3其实是不必更换位置的,因为它是序列末尾的上升子序列中的元素。

由于本题中必须是更改序列的第一个数,所以分析序列末的数字,只要上升的就一定不必要更改,因为只要前面的数字插入它们就好了。

例如题目中的1 2 4 3。序列末的上升子序列是3,所以3是肯定不会有更改的。

其他例子:4 6 7 2 5 9.序列末的上升子序列是2 5 9,所以这三个数字的位置肯定不会更改。

这就得到了输出的第一行,我们只要记录序列末上升子序列的长度len,再记ans=n-len并输出就好了。



得到了哪些元素需要修改哪些元素不需要修改后,就可以开始考虑怎样插入,移动几位了。

依旧对于序列4 6 7 2 5 9,考虑第一位4,我们可以首先将它放在2 5 9这组数据的前面,再考虑插入到哪一位(实际上是一个步骤)。前一个步骤可得到答案应当是ans-i,可是对于另开一个数组线性地搜索,这种解法显然不够优。我们可以考虑利用树状数组优化常数。

将2 5 9加入树状数组(注意是对其数值加一,即应当是 add(a[i],1);, ),所以只要搜索 sum(a[i]-1); 就可以了。

对于后面的元素也是一样的处理。得到最终的输出 printf("%d ",ans-i+sum(a[i]-1)); 。输出完后继续将数据加入树状数组。



代码:
#include<iostream>
#include<cstdio>

using namespace std;

const int N=1e5+5;
int n,a[N];
int ans=1;
int c[N];

int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int v)
{
    while(x<=n)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}

int sum(int x)
{
    int res=0;
    while(x)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    
    for(int i=n-1;i>=1;--i)
        if(a[i]<a[i+1])    ++ans;
        else    break;//记录序列末上升子序列长度
    printf("%d\n",n-ans);
    
    for(int i=n;i>n-ans;--i)
        add(a[i],1);//构建树状数组
    
    for(int i=1;i<=n-ans;++i)
    {
        printf("%d ",n-ans-i+sum(a[i]-1));//得到移动次数
        add(a[i],1);//不要忘记加入树状数组!
    }
    
    return 0;
}

 

上一篇:BZOJ2287: 【POJ Challenge】消失之物(背包dp)


下一篇:bzoj2287. 【POJ Challenge】消失之物