| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
我用最小后缀来做为什么是wa?求指正(附代码)#include<iostream>
using namespace std;
const int maxn=2000005;
int num[maxn];
int MinCircularDenote(const int* s, int len) {
int p1 = 0, p2 = 1, k, t1, t2;
while (1) {
k = 0;
while (1) {
t1 = (p1+k)%len; t2 = (p2+k)%len;
if(s[t1] > s[t2]) {
if (p1+k+1 <= p2) p1 = p2+1; // optimize
else p1 = p1+k+1;
if (p1 >= len) return p2; // p1 has checked len, return p2
break;
}
else if (s[t1] < s[t2]) {
if (p2+k+1 <= p1) p2 = p1+1;
else p2 = p2+k+1;
if (p2 >= len) return p1;
break;
}
else k++;
if (k == len) // has macthed len,return Min pos
return (p1<p2 ? p1 : p2);
}
}
}
int main(){
int n,i,j;
cin>>n;
for(i=n-1;i>=0;i--)
cin>>num[i];
int f1=MinCircularDenote(num+2,n-2)+2;
int f2=MinCircularDenote(num+1,f1-1)+1;
for(i=f1;i<n;i++)
cout<<num[i]<<endl;
for(i=f2;i<f1;i++)
cout<<num[i]<<endl;
for(i=0;i<f2;i++)
cout<<num[i]<<endl;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator