Alice's Print Service(二分+RMQ|线段树)

Alice is providing print service, while the pricing doesn't seem to be reasonable, so people using her print service found some tricks to save money.
For example, the price when printing less than 100 pages is 20 cents per page, but when printing not less than 100 pages, you just need to pay only 10 cents per page. It's easy to figure out that if you want to print 99 pages, the best choice is to print an extra blank page so that the money you need to pay is 100 × 10 cents instead of 99 × 20 cents.
Now given the description of pricing strategy and some queries, your task is to figure out the best ways to complete those queries in order to save money.

Input

The first line contains an integer T (≈ 10) which is the number of test cases. Then T cases follow.
Each case contains 3 lines. The first line contains two integers n, m (0 < n, m ≤ 10 5 ). The second line contains 2n integers s 1, p 1 , s 2, p 2 , ..., s n, p n (0=s 1 < s 2 < ... < s n ≤ 10 9 , 10 9 ≥ p 1 ≥ p 2 ≥ ... ≥ p n ≥ 0).. The price when printing no less than s i but less than s i+1 pages is p i cents per page (for i=1..n-1). The price when printing no less than s n pages is p n cents per page. The third line containing m integers q 1 .. q m (0 ≤ q i ≤ 10 9 ) are the queries.

Output

For each query q i, you should output the minimum amount of money (in cents) to pay if you want to print q i pages, one output in one line.

Sample Input

1
2 3
0 20 100 10
0 99 100

Sample Output

0
1000
1000

给出不同范围内的价格,求最少需要花多少钱

对于每一个询问,二分找到其所在区间,然后比较打印正好的页数的价格和多于要求页数的价格(即区间端点),求一个最小值

暴力妥妥的超时,然后套上了线段树,WA了好多次

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f3f3f3fLL;
const int N=1e5+20;
ll a[N],b[N],T[4*N+50];
void pushup(int k)
{
    T[k]=min(T[k*2],T[k*2+1]);
}
void build(int l,int r,int k)
{
    if(l==r)
    {
        T[k]=a[l]*b[l];
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,k*2);
    build(mid+1,r,k*2+1);
    pushup(k);
}
ll Q(int L,int R,int x,int y,int k)
{
    if(L==x&&R==y)///要找到准确的对应的区间
        return T[k];
    int mid=(L+R)/2;
    if(y<=mid)
    {
        return Q(L,mid,x,y,k*2);///需要查询的区间都在同一侧,可以直接返回
    }
    else if(x>mid)
    {
        return Q(mid+1,R,x,y,k*2+1);
    }
    else
        return min(Q(L,mid,x,mid,k*2),Q(mid+1,R,mid+1,y,k*2+1));///将需要查询的区间由mid分割成两部分
}
int main()
{
    ll n,m;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(T,inf,sizeof(T));
        scanf("%lld%lld",&n,&m);
        for(int i=1; i<=n; i++)
            scanf("%lld%lld",&a[i],&b[i]);
        build(1,n,1);
        ll p;
        while(m--)
        {
            scanf("%lld",&p);
            ll ans;
            if(p>=a[n])
                ans=p*b[n];
            else if(p==0)
                ans=0;
            else
            {
                ll id=lower_bound(a+1,a+n+1,p)-a;
//                cout<<id<<'\n';
                if(id>=1&&id<=n)
                {
                    if(a[id]>p)
                        id--;
//                cout<<ans<<'\n';
                    ans=min(b[id]*p,Q(1,n,id+1,n,1));
                }
                else
                    ans=p*b[n];
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

RMQ 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m;
ll a[N],b[N];
ll f[N][20];///f[i][j]表示从i位起2^j个数中的最大值,即【i,i+(1<<j)-1】
void ST_prework()
{
    for(int i=1; i<=n; i++)
        f[i][0]=a[i]*b[i];
    ll imax=(ll)(log(n*1.0)/log(2.0));
    for(int i=1; i<=imax; i++)
    {
        for(int j=1; j+(1<<i)-1<=n; j++) ///右端点为j+(1<<i)-1,-1是因为要包含j自己
            f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);
    }
}
ll ST_query(ll l,ll r)///求(l,r)中的最大值
{
    ll k=(ll)(log((l-r+1)*1.0)/log(2.0));///区间长度r-l+1
    return min(f[l][k],f[r-(1<<k)+1][k]);///第1个区间:[l,l+(1<<k)-1];第2个区间:(r,(1<<k)+1~r)
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
            scanf("%lld%lld",&a[i],&b[i]);
        ST_prework();
//        cout<<a[1]<<' '<<a[2]<<' '<<b[1]<<' '<<b[2]<<'\n';
        while(m--)
        {
            ll q,ans;
            scanf("%lld",&q);
            ll id=lower_bound(a+1,a+n+1,q)-a;
//            cout<<id<<'\n';
            if(id>n||a[id]>q)
                id--;
            ans=q*b[id];
//            cout<<ans<<'\n';
            if(id<n)
                ans=min(ans,ST_query(id+1,n));
            cout<<ans<<'\n';
        }
    }
    return 0;
}

 

全部评论

相关推荐

06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务