Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我用最小后缀来做为什么是wa?求指正(附代码)

Posted by gamy at 2010-05-07 17:05:13 on Problem 3581
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator