[BZOJ2882]工艺

• 链接
• • 博客链接
  • 题目链接
• 题目内容
• • 题目描述
  • 题目大意
  • 格式
  • • 输入
    • 输出
• 数据
• • 样例
  • • 输入
    • 输出
  • 数据范围
• 题解
• • • 40分
    • 100分

题目名称：工艺

来源：大视野在线测评

链接

博客链接

• 博客园
• 洛谷博客
• 洛谷题解

题目链接

• 大视野在线评测(2882)
• 洛谷(P1368)
• 入门OJ(2767)

题目内容

题目描述

小敏和小燕是一对好朋友。

他们正在玩一种神奇的游戏，叫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

题解

40分

暴力找最小表示，时间复杂度 O ( n 2 ) O(n^2) O(n2)。

100分

最小表示法裸题。

//C++
#include<bits/locale_facets.h>
#include<stdio.h>
using namespace std;
void output(long long o);
int flaw[300001];
template<typename name>name* expression(name* l,name* r);
long long input();
int main()
{
	int n=input();
	for(int i=1;i<=n;i++)flaw[i]=input();
	int answer=expression<int>(flaw+1,flaw+n)-flaw;
	for(int i=answer;i<=n;i++)output(flaw[i]),putchar(' ');
	for(int i=1;i<answer-1;i++)output(flaw[i]),putchar(' '); 
	output(flaw[answer-1]),putchar('\n');
	return 0;
}
void output(long long o)
{
	if(o<0)putchar('-'),o=-o;
	if(o>=10)output(o/10);
	putchar(o%10+'0');
}
template<typename name>name* expression(name* l,name* r)
{
	int n=r-l,i=0,j=1;
	for(int k=0,I,J,bound;i<=n&&j<=n&&k<=n;)
	{
		I=(i+k-1)%n+1,J=(j+k-1)%n+1;
		if(l[I]==l[J])k++;
		else
		{
			if(l[I]<l[J])swap(i,j);
			bound=max(i+k,j-1);
			if(i<j)j=bound+2;
			i=bound+1,k=0;
		}
	}
	return l+min(i,j);
}
long long input()
{
	bool positive=true;
	char NUM=getchar();
	long long i=0;
	for(;!isdigit(NUM);NUM=getchar())
	if(NUM=='-')positive=!positive;
	for(;isdigit(NUM);NUM=getchar())i=(i<<3)+(i<<1)+NUM-'0';
	return positive?i:-i;
}