郑州富士康招聘信息,天天向上 古晨,错了错了广播剧
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("%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;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论