发布于 由itewqq

[比赛][线段树][模拟] 2018南京网络赛 G Lpl and Energy-saving Lamps

这题真的好鸡儿简单。。。差不多是除了第一题之外最简单的了。比赛的时候没看这个，iSika说很难就没做，唉

题意：给n个房间，当还有房间的灯没有被换成节能灯的时候每个月开始会买入m个节能灯，然后从左向右在列表中找小于m的房间换掉，如果当月的节能灯没有用完的话可以留给下个月。然后给q个询问问d第几个月结束的时候有多少个房间被换成了节能灯，以及手里剩下了多少节能灯。

解法：用value表示当前总共有多少个节能灯，把q个询问都读进来排序后从小到大操作（就是从第一个月开始模拟）。每次都找列表中<=value的最左边的值，找的方法是用线段树维护区间minv 信息，如果左子树minv<=value的话就向左走否则向右，如果小于minv[1]就不找，直接把当月的算出来。找到的话，令找到的房间的计数器+1，value-=找到的值，然后更新线段树这个点的minv为INF就行了。由于每个节点最多被修改一次，修改一次的代价为logn，所以总共的代价为qlogn，case closed！

 

#include
#include
#include
#include
#include
#include
#include
#include

#include

using namespace std;
const int maxn=1e5+5;
typedef long long LL;

int k[maxn],qs[maxn],ans1[maxn],ans2[maxn];

const int maxnode = (maxn<<2); const int INF = 1000000000; int minv[maxnode]; int p,v; void update(int o,int l,int r) { if(l==r) minv[o]=v ; else { int m=(l+r)>>1;
        if(p<=m)update(o<<1,l,m);
        else update((o<<1)+1,m+1,r);
        minv[o]=min(minv[o<<1],minv[o<<1|1]); } } int ql,qr,pos,value,cnt; void query(int o,int l,int r) { if(minv[o]>value)
        return ;
    if(l==r&&minv[o]<=value) { cnt++; value-=minv[o]; pos=l; } else { int m=(l+r)>>1;
        if(minv[o<<1]<=value)query(o<<1,l,m);
        else query(o<<1|1,m+1,r);
    }
    return ;
}

int main()
{
    int n,m,q,mq=0;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&k[i]);
        p=i,v=k[i];
        update(1,1,n);
    }
    scanf("%d",&q);
    for (int i=1; i<=q; i++)
    {
        scanf("%d",&qs[i]);
        mq=max(qs[i],mq);
    }
    value=0;
    cnt=0;
    //cout<<"n   "<<n<<endl;
    for (int i=1; i<=mq; i++)
    {
        if(cnt<n)value+=m;
        while(minv[1]<=value)//error1
        {
            pos=n+5;
            query(1,1,n);
            p=pos,v=INF;
            update(1,1,n);
        }
        ans1[i]=cnt,ans2[i]=value;
    }
    for (int i=1;i<=q;i++)
    {
        printf("%d %d",ans1[qs[i]],ans2[qs[i]]);
        if(i!=q)
            puts("");
    }
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。