【bzoj2882】工艺

2015.06.12 19:50 Fri | 11次阅读 | 旧日oi | 固定链接 | 源码

Description

给定一个序列,求从哪个位置开始表示这个序列的字典序最小。

Input

最小表示法裸题,贴模板

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,a[300005];
int mp()
{
    int i=0,j=1,k=0,t;
    while(i<n&&j<n&&k<n)
    {
        t=a[(i+k)%n]-a[(j+k)%n];
        if(!t) k++;
        else 
        {
            if(t>0) i+=k+1;
            else j+=k+1;
            if(i==j) i++;
            k=0;
        }
    }
    return min(i,j);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    int t=mp();
    printf("%d",a[t]);
    for(int i=1;i<n;i++) printf(" %d",a[(t+i)%n]);
}```