题解 P1368 【工艺】

千年知乎_天才 · 2019-09-20 16:09:26 · 题解

题目名称：工艺

来源：大视野在线测评

链接

博客链接

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

题目链接

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

题解

题目大意

给出一个数字串，求其最小表示。

40分

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

100分

最小表示法裸题，不会的可以通过链接进入我的博客学习。

//C++
#include<bits/locale_facets.h>
#include<stdio.h>
#define forto(name,i,d,u) for(name i=d;i<=u;i++)
#define foruntil(name,i,d,u) for(name i=d;i<u;i++) 
using namespace std;
inline void output(long long o);
inline long long input();
int flaw[300001];
template<typename name>name* expression(name* l,name* r);
int main(){ 
    int n=input();
    forto(int,i,1,n)flaw[i]=input();
    int answer=expression<int>(flaw+1,flaw+n)-flaw;
    forto(int,i,answer,n)output(flaw[i]),putchar(' ');
    answer--;
    foruntil(int,i,1,answer)output(flaw[i]),putchar(' '); 
    output(flaw[answer]),putchar('\n');
    return 0;
}inline long long input(){
    bool minus=false;
    char now=getchar();
    long long i=0;
    for(;!isdigit(now);now=getchar())
    if(now=='-')minus=!minus;
    for(;isdigit(now);now=getchar())i=(i<<3)+(i<<1)+(now^'0');
    return minus?-i:i;
}inline 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);
}