| ||||||||||
| 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