老师，那还需要用二分吗，好像也超时。。。60分
1 个赞
改完的代码：
超时60分
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
int n;
int num;
int sit;
}re[200005];
bool cmp(node a,node b)
{
return a.num<b.num;
}
bool cmp2(node a,node b)
{
return a.n<b.n;
}
int n,q,a[200005],b[200005],sum[200005];
signed main(void)
{
cin>>n>>q;
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<=q;i++)
{
cin>>b[i];
re[i].n=i;
re[i].num=b[i];
}
sort(re+1,re+1+q,cmp);
for(int i=1;i<=q;i++)
{
for(int j=1;j<=n;j++)
{
if(a[j]>re[i].num)
{
break;
}
else
{
re[i].sit=j;
}
}
}
sort(re+1,re+1+q,cmp2);
for(int i=1;i<=q;i++)
{
cout<<sum[re[i].sit]<<" ";
}
return 0;
}
1 个赞
你有没有想过双循环该怎么处理？那么明显的双循环不能用二分来来替换吗？
2 个赞
一个非常简单的模板题目，告诉你二分的思路不过是需要预处理一下最高高度，说明你二分掌握的非常不好，去把我们课堂上的题目再做几遍，并且自己反思总结。
第一步：构造一个数组用来存储到此之前最高的高度
第二步：在q次循环中，对输入的数值进行二分，去寻找能走的最大高度
不就得了吗？
核心代码
while (l < r) {
int mid = (l + r + 1) >> 1;
if (a[mid] <= x) {
l = mid;
} else {
r = mid - 1;
}
}
这里a数组用来存储到到当前阶梯之前的最高高度，x就是当前的Bi
2 个赞
好的老师，太太太太太太太感谢了。
AC啦
1 个赞