【计蒜客】2018ICPC南京赛区网络赛G Lpl and Energy-saving Lamps（线段树）

题目链接

 

【题意】

题目很长，但是题意还是能读懂的。有n个房间，里面分别由ai盏灯需要更换，Lpl每天都会买m盏灯，如果刚好能更换一个房间就会把灯都更换掉，如果不能就会继续找下一个房间看是否能全部更换，剩余的灯就会被留到第二天使用，最后输出她每天最多能更换的房间数和所剩余的灯的数量。

【解题思路】

每次更换节能灯需要得到节能灯需求数目小于拥有数目的房间编号，那么我们可以通过线段树维护区间最小值，查询的时候优先查询更左边最小值小于等于拥有数目的区间，就可以保证查询到的是满足要求且房间编号最小的房间。当存在这样一个房间时，返回房间编号，然后更新拥有的节能灯数目，同时将该房间要求数量更新为INF，即可保证不影响后面的操作；否则返回0，代表目前已经没有比要求的比拥有的节能灯数目更小的房间了。最后将每天的房间数和剩余灯的数量存进数组，这样就可以线性查询了。

https://blog.csdn.net/qq_38515845/article/details/82292389

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=0x3f3f3f3f;
const int maxn=1e5+5;
LL n,m;
LL tree[4*maxn+1],a[maxn],num[maxn],ans[maxn],sum=0;
void build(int id,int l,int r)
{
    if(l==r)
    {
        tree[id]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    tree[id]=min(tree[id*2],tree[id*2+1]);
}
void update(int x,int id,int l,int r,LL y)
{
    if(l==r)
    {
        tree[id]=y;
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid)
        update(x,id*2,l,mid,y);
    else
        update(x,id*2+1,mid+1,r,y);
    tree[id]=min(tree[id*2],tree[id*2+1]);
}
int query(int id,int l,int r,int x)
{
    if(l==r)
    {
        if(tree[id]<=sum)
        {
            num[x]++;
            ans[x]=sum-tree[id];
            sum-=tree[id];
            update(l,1,1,n,INF);
            return 1;
        }
        else if(num[x]==0)
        {
            num[x]=num[x-1];
            ans[x]=sum;
        }
        return 0;
    }
    int mid=(l+r)/2,res;
    if(tree[2*id]<=sum)
        res=query(id*2,l,mid,x);
    else
        res=query(id*2+1,mid+1,r,x);
    return res;
}
void work(int i)
{
    int flag=0;
    while(query(1,1,n,i))flag=1;
    if(flag)num[i]+=num[i-1];
}
int main()
{
    int q;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=maxn;i++)
    {
        sum+=m;
        if(num[i-1]==n)
        {
            num[i]=num[i-1];
            ans[i]=ans[i-1];
        }
        work(i);
    }
    scanf("%d",&q);
    while(q--)
    {
        int x;
        scanf("%d",&x);
        printf("%lld %lld\n",num[x],ans[x]);
    }
    return 0;

}