1 solutions
Information
- ID
- 6684
- Time
- 500ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- # Submissions
- 103
- Accepted
- 12
- Uploaded By
这个题的题意很简单,就是计算p体力可以到达的最远营地,我们可以根据每2个营地之间的距离计算出从0开始到第i个营地之间的距离,构造出前缀和数组来保存这个距离。由于距离非负,前缀和数组是单调递增的,我们可以使用二分法来找到不超过p的最大值在前缀和数组中的位置,得到的就是问题的答案。
附代码:
#include<bits/stdc++.h>
using namespace std;
int n,q,i;
long long a[100100]={0};
long long sum[100100]={0};
int erfen(int x)//二分查找不大于x的最大元素的位置
{
int left=0,right=n+1,mid;
while (left+1<right)
{
mid=(left+right)/2;
if (x<sum[mid])
{
right=mid;
}
else
{
left=mid;
}
}
return left;
}
int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
scanf("%d",&q);
for (i=1;i<=q;i++)
{
int k,ans;
scanf("%d",&k);
ans=erfen(k);
printf("%d\n",ans);
}
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.