欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

P5200 [USACO19JAN]Sleepy Cow Sorting

程序员文章站 2022-06-20 23:11:37
P5200 [USACO19JAN]Sleepy Cow Sorting 题目描述 Farmer John正在尝试将他的N头奶牛(1≤N≤10^5),方便起见编号为1…N,在她们前往牧草地吃早餐之前排好顺序。 当前,这些奶牛以p1,p2,p3,…,pN的顺序排成一行,Farmer John站在奶牛p ......

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