P1368 工艺
题目描述
小敏和小燕是一对好朋友。
他们正在玩一种神奇的游戏,叫Minecraft。
他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的,而且由于机器的要求,他们只能做到把这个工艺品最左边的方块放到最右边。
他们想,在仅这一个操作下,最漂亮的工艺品能多漂亮。
两个工艺品美观的比较方法是,从头开始比较,如果第i个位置上方块不一样那么谁的瑕疵度小,那么谁就更漂亮,如果一样那么继续比较第i+1个方块。如果全都一样,那么这两个工艺品就一样漂亮。
输入输出格式
输入格式:
第一行两个整数n,代表方块的数目。
第二行n个整数,每个整数按从左到右的顺序输出方块瑕疵度的值。
输出格式:
一行n个整数,代表最美观工艺品从左到右瑕疵度的值。
输入输出样例
10
10 9 8 7 6 5 4 3 2 1
1 10 9 8 7 6 5 4 3 2
说明
对于20%的数据,n<=1000
对于40%的数据,n<=10000
对于100%的数据,n<=300000
Solution:
本题可以用后缀数组做(但是至少我现在不会,~挖坑了~),然后学了一下最小最大表示法,这题目就迎刃而解了。
题意即对于这个循环序列,求它的字典序最小的序列。
由于所求序列与原序列同构,所以只要知道这个字典序最小的序列的头指针在原序列中的位置就$OK$了。
最小最大表示法其实很简单,直接设两个指针$i=0,j=1$($i,j$小于字符串长度$lenth$),比较:
1、$s[i]<s[j]$,则$j++$;
2、$s[i]>s[j]$,则$i=j,j=i+1$;
3、$s[i]==s[j]$,则另取辅助指针$k$,一直往后扫:当$while(s[i+k]==s[j+k])$则$k++$,当$s[i+k]>s[j+k]$则$i=i+k$,当$s[i+k]<s[j+k]$则$j++$。
这样最后返回$pos=min(i,j)$,则$pos$即所求的原序列的同构序列中,字典序最小的序列头指针在原序列中的下标了。
这样去求复杂度是$O(n)$的,为什么呢?原因很简单,因为我们$i,j$都没有往回退的过程,只会往前走,那么到了边界也就结束了。
代码:
#include<bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
const int N=3e5+;
int n,a[N],i,k;
il int gi(){
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=;
while(x>=''&&x<='')a=a*+x-,x=getchar();
return f?-a:a;
}
il int getmin(int *s){
int i=,j=,l;
while(i<n&&j<n){
for(l=;l<n;l++)
if(s[(i+l)%n]!=s[(j+l)%n])break;
if(l>=n)break;
if(s[(i+l)%n]>s[(j+l)%n])i+l+>j?i+=l+:i=j+;
else if(j+l+>i)j+=l+;
else j=i+;
}
return i<j?i:j;
}
int main()
{
n=gi();
for(i=;i<n;i++)a[i]=gi();
k=getmin(a),i=;
while(i<n){
printf("%d ",a[k]);
k=(++k)%n;
i++;
}
return ;
}
最新文章
- js第三方
- Evolutionary Computing: 3. Genetic Algorithm(2)
- cJSON_json包的C语言解析库
- 文件中的类都不能进行设计,因此未能为该文件显示设计器。设计器检查出文件中有以下类: FormMain --- 未能加载基类“WinForm.Win.FormsBase.FormMainBase”。请确保已引用该程序集并已生成所有项目
- 【转】循环递归遍历XML文档或按某要求遍历XML文档
- 【技术贴】同一台机器Tomcat7多版本共存配置文档
- ObjectStreamDemo
- lucene Filter过滤器
- 分布式事务的典型处理方式:2PC、TCC、异步确保和最大努力型
- LESS的好处
- 求二维数组的最大子数组———曹玉松&;&;蔡迎盈
- es6之三个点(...)扩展运算符
- xshell连接虚拟机ubuntu
- CCF后感
- centos-1 nginx
- ubuntu下cmake编译opencv 3.4.3源码;
- CSS 初知
- Sqlserver精简安装选项
- poj 1125 谣言传播 Floyd 模板题
- Oracle_SQL(6) 单行函数