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.h" #include "string.h" #include "stdlib.h" #include "fstream.h" const long int maxn=110000; long int h[maxn],f[maxn],n,len,b,e,ans; int sort(long int b,long int e) { long int i=b,j=e,mid=h[f[rand()%(e-b)+b]],k; while(i<=j) { while(h[f[i]]<mid) i++; while(h[f[j]]>mid) j--; if (i<=j) { k=f[i]; f[i]=f[j]; f[j]=k; i++; j--; } } if (b<j) sort(b,j); if (i<e) sort(i,e); return 0; } long int find(long int cost) { long int b=0,e=n; while(e-b>1) if (h[f[(b+e)/2]]>=cost) e=(b+e)/2; else b=(b+e)/2; while(b>0) if (h[f[b]]!=h[f[b-1]]) return b; else b--; return b; } int check(long int k,long int t,long int c) { if (f[k]==t) return 0; long int cost=abs(h[f[k]]-c); if (cost<ans) { ans=cost; if (f[k]<t) { b=f[k]+1; e=t; } else { b=t+1; e=f[k]; } } return 0; } int out() { long int i; for (i=0;i<=n;i++) cout<<h[f[i]]<<' '; cout<<endl; return 0; } int main() { // ifstream cin ("1.in"); // ofstream cout ("1.out"); while(true) { cin>>n>>len; if ((n==0)&&(len==0)) break; long int i,j; h[0]=0; for (i=1;i<=n;i++) { cin>>h[i]; h[i]+=h[i-1]; } for (i=0;i<=n;i++) f[i]=i; sort(0,n); //out(); for (i=1;i<=len;i++) { long int k,k1,cost,l; ans=214748000; cin>>k; for (j=0;j<=n;j++) for (l=0;l<2;l++) { if (l==0) cost=h[j]+k; else cost=h[j]-k; k1=find(cost); check(k1,j,cost); k1++; while((h[f[k1]]==h[f[k1-1]])&&(k1<n)) { check(k1,j,cost); k1++; } do { check(k1,j,cost); k1++; } while((k1<=n)&&(h[f[k1]]==h[f[k1-1]])); } if (b==0) ans=abs(h[e]); else ans=abs(h[e]-h[b-1]); cout<<ans<<' '<<b<<' '<<e<<endl; } } // cout.close(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator