题解 P1314 【聪明的质监员】

· · 题解

这道题考试时候gg

后来做分数0->85->95->AC (捂脸)

0是我样例对了但有个判断“==”号写成了“=”(捂脸）

85分是有几个变量写成int，估计数据里有long long的（捂脸）

最后只剩第13个点错然后一脸懵逼（捂脸）

说说这道题

这题和P1880石子合并题很像

循环用二分法求p-y最小时W（也就是重量标准）

通过前缀和数组来存合格的石头的总价“av ”(不要想多，这就是个变量名代表总v）和石头总数“an "

通过av[范围右顶点]-av范围左顶点-1就可以算出这段范围里的石头总价（总数同理）

否则每次都需要遍历每一个石头很费时间（估计会TLE）

先看一下95分程序

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,m;
long long s;
long long av[200010],an[200010];
struct st
{
    long long w,v;
}stone[200010];
struct ra
{
    long long l,r;
}range[200010];
int main()
{
    cin>>n>>m>>s;
    long long right=-1;
    for(long long i=1;i<=n;i++)
    {
        cin>>stone[i].w>>stone[i].v;
        right=stone[i].w>right?stone[i].w:right;
    }
    for(long long i=1;i<=m;i++)
        cin>>range[i].l>>range[i].r;
    long long left=0;
    long long minn=-1,p;
    while(left<right)//错误1
    {
        long long mid=(left+right)/2;
        av[0]=0,an[0]=0;
        for(long long i=1;i<=n;i++)
        {
            if(stone[i].w>=mid)
            {
                av[i]=av[i-1]+stone[i].v;
                an[i]=an[i-1]+1;
            }
            else 
            {
                av[i]=av[i-1];an[i]=an[i-1];    
            }
        }
        long long p=0;
        for(long long i=1;i<=m;i++)
        {
            p+=(av[range[i].r]-av[range[i].l-1])*(an[range[i].r]-an[range[i].l-1]);    
        }
        if(minn==-1 || minn>abs(p-s)) minn=abs(p-s);
        if(p<s)right=mid;//错误2
        else left=mid+1;
    }
    cout<<minn;
    return 0;
}

为什么是95分?

第十三个点没过我觉得有两个原因:

错误1：要改成"left<=right"因为mid=left=right时也要判断是否成立

错误2：要改成right=mid-1因为在某个极限数据中，当left=right-1（相差1）会进入死循环gg

改完之后就AC了0v0

代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long n,m;
long long s;
long long av[200010],an[200010];
struct st//存石头数据
{
    long long w,v;
}stone[200010];
struct ra//存范围数据
{
    long long l,r;
}range[200010];
int main()
{
    cin>>n>>m>>s;
    long long right=-1;
    for(long long i=1;i<=n;i++)
    {
        cin>>stone[i].w>>stone[i].v;
        right=stone[i].w>right?stone[i].w:right;//求出石头最大重量作为 第一次二分的上限
    }
    for(long long i=1;i<=m;i++)
        cin>>range[i].l>>range[i].r;
    long long left=0;
    long long minn=-1,p;
    while(left<=right)//开始循环
    {
        long long mid=(left+right)/2;//二分可行域
        av[0]=0,an[0]=0;
        for(long long i=1;i<=n;i++)
        {
            if(stone[i].w>=mid)
            {
                av[i]=av[i-1]+stone[i].v;//前缀和数组
                an[i]=an[i-1]+1;
            }
            else 
            {
                av[i]=av[i-1];an[i]=an[i-1];    
            }
        }
        long long p=0;
        for(long long i=1;i<=m;i++)
        {
            p+=(av[range[i].r]-av[range[i].l-1])*(an[range[i].r]-an[range[i].l-1]);    
        }
        if(minn==-1 || minn>abs(p-s)) minn=abs(p-s);
        if(p<s)right=mid-1;//准备下一次二分的上限或下限
        else left=mid+1;
    }
    cout<<minn;
    return 0;
}