| input | output |
|---|---|
5 1 4 1 2 3 4 5 4 |
8 |
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
using namespace std;
const int maxn=1e5;
int T[maxn],a[maxn],sum[maxn];
int n,t,k;
int solve(int x)//二分得大于x的最小位置i
{
int l=0,r=n;
int ans;
while(l<=r)
{
int mid=(l+r)>>1;
if(sum[mid]<x)
{
ans=mid;
l=mid+1;
}
else
r=mid-1;
}
return ans;
}
int main()
{
while(cin>>n>>t>>k)
{
sum[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=t;i++)
cin>>T[i];//第几秒
t++;
T[t]=2000000000;//最后没有分心时间的时候可以做if语句做完事情
int pos=0,to;
int ans=0;
for(int i=1;i<=t;i++)
{
if(n-pos<T[i]-ans)//T[i]时间内可以做完
{
ans+=n-pos;
break;
}
else
{
to=T[i]-ans+pos;//分心的时候到了第几个位置及当前位置pos加上还要走的距离(T[i]-ans);
ans+=T[i]-ans;//ans,当前走了多少时间
pos=solve(sum[to-1]-k);//找到分心后的位置
}
}
cout<<ans<<endl;
}
return 0;
}
(校赛）URAL 1998 The old Padawan,布布扣,bubuko.com
原文：http://blog.csdn.net/u013582254/article/details/38256445