第一道绿题，第一发就过了70%（QAQ泪目），剩下都超时了，不知道该怎么优化了，看了解析，才知道需要使用前缀和。太妙了，题说给m个区间，n个矿石，要求这m个区间y的值的和，可以直接算从1到n的和，然后使用prev1[r[j]]-prev1[l[j]-1]算出各个区间和。
代码：
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int n,m,s;
int w[200010],v[200010],l[200010],r[200010];
//int prev1[200010]={0},prev2[200010]={0};
int y_is(int W)
{
int h=0,s1=0,s2=0;
// for(int j=1;j<=m;j++){
// s1=0,s2=0;
// for(int i=l[j];i<=r[j];i++)
// {
// if(w[i]>=W)
// {s1+=1;s2+=v[i];}
// }
// h+=(s1*s2);
// //cout<<h<<"\n";
// }
int prev1[200010]={0},prev2[200010]={0};
for(int j=1;j<=n;j++)
{
if(w[j]>=W)
{prev1[j]=prev1[j-1]+1;
prev2[j]=prev2[j-1]+v[j];
}
else{
prev1[j]=prev1[j-1];
prev2[j]=prev2[j-1];
}
}
for(int j=1;j<=m;j++)
{
h+=(prev1[r[j]]-prev1[l[j]-1])*(prev2[r[j]]-prev2[l[j]-1]);
}
return h;
}
signed main()
{
cin>>n>>m>>s;
for(int i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
}
for(int i=1;i<=m;i++)
{
cin>>l[i]>>r[i];
}
int max=w[0],min=w[0];
for(int i=1;i<=n;i++)
{
if(max<w[i])
max=w[i];
if(min>w[i])
min=w[i];
}
int i=min-1,j=max+1;
while(i+1!=j)
{
int mid=(i+j)/2;
if(y_is(mid)<=s)j=mid;
else i=mid;
}
int x=abs(y_is(i)-s),y=abs(y_is(j)-s);
if(x<y)
cout<<x;
else cout<<y;
//cout<<"aa"<<y_is(4);
// int *b,*c;
// b=max_element(w,w+n);
// c=min_element(w,w+n);
}
要注意的点：
1、发现把前缀和的初始化放在子函数里和子函数外都ac了，发现计算前缀和时，是从prev[0]开始计算的，而prev[0]恒等于0！所以每次计算都会重新赋值，prev初始化在该函数外也不怕叠加，会被覆盖，所以以后计算前缀和要从下标为1开始，下标为0的初值设置为0。
2、再就是二分判断的条件要想明白，如果y小于s，就说明W设置的太大了，需要往左边找（r=mid）
标签：前缀,int,prev1,每日,mid,200010,聪明,质检员,prev2 From： https://blog.csdn.net/m0_73997108/article/details/143266944