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