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次操作过后奶牛们应该排好了顺序。
如果存在多种最优的操作序列,你的程序可以输出其中任何一种。
输入输出样例
4 1 2 4 3
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("%dn",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; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/602183.html