|
|
back to boardmy algo with O(N) get WA#1!! Posted by Bobur 24 Nov 2008 01:55 please help, i can't find my mistake!!! Re: my algo with O(N) get WA#1!! My algorithm is O(n*(n-k)) but I can't pass test 1 too, Help me, if you can. this is my code. # include <iostream> using namespace std; int main () { char a; int min,num,n,k,i,ans=0; int w[510]={0}; int b[510]={0}; cin>>n>>k; for(i=0;i<n;i++) { cin>>a; if(a=='0') b[i]=1; else w[i]=1; } while(n>k) { min=2147483647; for(i=0;i<n-1;i++) if(min>w[i]*b[i+1]+w[i+1]*b[i]) { min=w[i]*b[i+1]+w[i+1]*b[i]; num=i; } w[num]+=w[num+1]; b[num]+=b[num+1]; for(i=num+1;i<n;i++) { w[i]=w[i+1]; b[i]=b[i+1]; } n--; ans+=min; } cout<<ans<<endl; return 0; }
|
|
|