个人中心
gpt4 book ai didi

P1314聪明的质监员（题解）

转载 作者：我是一只小鸟 更新时间：2022-12-19 22:31:07 24 4
gpt4 key购买 nike

题目

小 T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 \(n\) 个矿石，从 \(1\) 到 \(n\) 逐一编号，每个矿石都有自己的重量 \(w_i\) 以及价值 \(v_i\) 。检验矿产的流程是:

1 、给定 \(m\) 个区间 \([l_i,r_i]\) ； 。

2 、选出一个参数 \(W\) ； 。

3 、对于一个区间 \([l_i,r_i]\) ，计算矿石在这个区间上的检验值 \(y_i\) :

\[y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j \]

其中 \(j\) 为矿石编号.

这批矿产的检验结果 \(y\) 为各个区间的检验值之和。即： \(\sum\limits_{i=1}^m y_i\) 。

若这批矿产的检验结果与所给标准值 \(s\) 相差太多，就需要再去检验另一批矿产。小 T 不想费时间去检验另一批矿产，所以他想通过调整参数 \(W\) 的值，让检验结果尽可能的靠近标准值 \(s\) ，即使得 \(|s-y|\) 最小。请你帮忙求出这个最小值.

解析

这是一道比较清晰明了的二分答案.

可以看出整个式子的自变量是 \(W\) ，因变量是此时得到的 \(y\) .

那么就来判断是否可以运用二分来解，首先判断单调性:

当 \(W\) 比最轻的矿石质量还小时，所有的矿石都可以参与运算，计算出来的 \(y\) 必定最大.

当 \(W\) 比最重的矿石质量还大时，所有的矿石都不能参与运算，计算出来的 \(y\) 必定最小.

因此， \(W\) 越小，参与计算的数就越多， \(y\) 也就越大.

所以单调性出来了，我们就可以在区间内通过枚举 \(W\) 来得到答案了.

然后就 \(TLE\) 了…… 。

优化

查看代码发现，二分部分肯定是不会有什么超时的地方，那就是 check 函数的问题了.

发现在每次计算过程中由于重复计算造成了大量的浪费，于是考虑用前缀和优化.

使用 sum_n[i] 来表示区间中合格部分数量，sum_v[i] 来记录区间中合格部分价值.

最后进行计算.

                        
                          #include<iostream>
#include<algorithm>
#include<cstdio>
#define int long long

using namespace std;

int n,m,s;
int w[200500],v[200500];
int l[200500],r[200500];

int sum_n[200500],sum_v[200500];

long long ans = 0;

void init()
{
    scanf("%lld%lld%lld",&n,&m,&s);
    for(int i = 1;i <= n; i++)
        scanf("%lld%lld",&w[i],&v[i]);
    for(int i = 1;i <= m; i++)
        scanf("%lld%lld",&l[i],&r[i]);
    
    return ;
}

long long check(int W)
{
    long long ans = 0;
    for(int i = 1;i <= n; i++)
    {
        if( W > w[i] )// 要用前缀和，不然会炸掉！！！
        {
            sum_n[i] = sum_n[i-1];
            sum_v[i] = sum_v[i-1]; 
        }
        else
        {
            sum_n[i] = sum_n[i-1] + 1;
            sum_v[i] = sum_v[i-1] + v[i]; 
        }
    }

    for(int i = 1;i <= m; i++)
    {
        long long a,b;
        a = sum_v[r[i]] - sum_v[l[i]-1];
        b = sum_n[r[i]] - sum_n[l[i]-1];
        ans += a*b;
    }

    return ans;
}

long long _abs(long long a)
{
    if( a > 0 )
        return a;
    return -a;
}

signed main()
{
    init();

    int left = 0,right = 1000000,mid;

    while( left <= right )
    {
        mid  = (left + right)>>1;
        if( check(mid) > s )
            left = mid + 1;
        else    
            right = mid - 1;
    }
    ans = _abs(check(left) - s);
    
    if( _abs(check(right) - s) < ans )
        ans = _abs(check(right) - s);
    
    printf("%lld",ans);
    return 0;
}

总结

题总体来说并不算难，但细节仍需要注意.

例如在考试中，就很有可能会忘记前缀和优化的问题，导致失去 30 分.

还有一直存在的 long long 的问题，同样会影响数十分.

要注重时间复杂度，重视算法的优化。做题时一定要每道题计算时间复杂度，不然考场追悔莫及.

最后此篇关于P1314聪明的质监员（题解）的文章就讲到这里了,如果你想了解更多关于P1314聪明的质监员（题解）的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

24 4 0
文章推荐： Pytorch学习笔记之tensorboard
文章推荐： django框架(部分讲解)
文章推荐： 智能语音之远场关键词识别实践（二）
文章推荐： 高可用系列文章之三-NGINX高可用实施方案
我是一只小鸟
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com