线段树：Fair Shuttle

Cry_For_theMoon · 2020-09-23 18:32:32 · 题解

  传送门

  典型的"线段树只是工具人"题目

  大佬们竟然都没有怎么证明贪心？蒟蒻水社区分的机会到了

  把 m 个 s 到 e 的奶牛分开看作 m 个 s 到 e 的区间，这样就不用考虑区间的个数问题了。

  设 F_{i,j} 是地点 i...j 所能选择的最大区间数。

  按照区间贪心的套路，先试试右端点排序。我们假设 a_i 是所有在 i...j 这段里的区间中结束最早的那个。假设最优解没有 a_i。那么我们对最优解的所有区间的 左端点排序，把此时开始时间最早的区间记作 a_j。

• 如果a_i,a_j 不交，一定可以选择 a_i，此时不是最优解

• 如果a_j 完全包含 a_i，优先选 a_i 显然可以让后面剩下的资源更多，这是因为在原来的方案里 e_{a_i}...e_{a_j} 这一段的空间比优先选择 a_i 少1，那么必然解不会比选择 a_i 更优。

• 否则 s_{a_i} < s_{a_j},e_{a_i} < e_{a_j}，此时选择 a_i ，那么 e_{a_i}... e_{a_j} 这段空间就会多1，显然我们可以选择更多的奶牛上车，即至少不会得到更差解。

  综上，F_i,j 的最优解中一定有一个解是包含 结束时间最早的 那个活动的。

  不过这只是在最初的时候如此。考虑那个熟的不能再熟的区间调度问题，我们也不是一鼓作气把排完序以后找到最前面的一口气选择，而是找到第一个和上一个选择兼容的区间。这题稍有改动，我们如果要选择区间 a_i，那么必须保证 s_{a_i}...e_{a_i} 这一段里面的任何一个时刻值都是小于 c 的，而我们只需要维护最大值即可。

  最后，题目本身一个区间里是有 m 头奶牛的，通过我们上面的推断，如果选了第 i 个区间，那么尽可能多的先把第 i 个区间的奶牛选上，维护区间最大值 maxn，\min(m_i,c-maxn) 就是当前选择能选择的个数。选择完了以后把区间整体加上一个选择个数即可。

  本人本着代码能暴力就暴力的原则交了一发暴力代码上去，结果 64 分 TLE 泪目。不过看到"区间加""区间最大值"，这就是一个裸的线段树了。

  与多数线段树的题不同的是，这一题难的不是数据结构，而是贪心的猜测与证明（反正我一开始没想出来），所以题解都没有写证明让我很害怕QwQ

  当然，dalao们做贪心题都是"直觉猜测显然成立"的，只有我这种蒟蒻需要证明。

  献上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=5e4+10;
int n,k,ans,c;
struct Line{
    int m,l,r;
    bool operator<(const Line& l2)const{
        return r < l2.r;
    }
}line[MAXN];
int zt[MAXN];
int tree[MAXN<<2],tag[MAXN<<2];
inline int lc(int x){return x<<1;}
inline int rc(int x){return lc(x)|1;}
void push_up(int);
void push_down(int);
int query(int,int,int,int,int);
void update(int,int,int,int,int,int);
int main(){
    scanf("%d%d%d",&k,&n,&c);
    for(int i=1;i<=k;i++){
        scanf("%d%d%d",&line[i].l,&line[i].r,&line[i].m);
    }
    sort(line+1,line+1+k);
    for(int i=1;i<=k;i++){
        int l = line[i].l,r = line[i].r,m = line[i].m;
        //max [l,r)
        int maxn = query(1,1,n,l,r-1);
        int chose =((c-maxn) < m)?(c-maxn):m;
        ans += chose;
        //[l,r) += chose
        update(1,1,n,l,r-1,chose);
    }
    cout<<ans;
    return 0;
}
void push_up(int x){
    tree[x] = max(tree[lc(x)],tree[rc(x)]);
}
void push_down(int x){
    //只维护max甚至不需要l,r？
    tree[lc(x)] += tag[x];
    tree[rc(x)] += tag[x];
    tag[lc(x)] += tag[x];
    tag[rc(x)] += tag[x]; 
    tag[x] = 0; 
}
int query(int x,int l,int r,int ql,int qr){
    if(ql <= l && qr >= r){
        return tree[x];
    }
    int mid = (l+r)>>1;
    int ans = 0;
    push_down(x);
    if(ql <= mid){
        ans = max(ans,query(lc(x),l,mid,ql,qr));
    }
    if(qr > mid){
        ans = max(ans,query(rc(x),mid+1,r,ql,qr));
    }
    push_up(x);
    return ans;
}
void update(int x,int l,int r,int ql,int qr,int value){
    if(ql <= l && qr >= r){
        tree[x] += value;
        tag[x] += value;
        return;
    }
    int mid = (l+r)>>1;
    push_down(x);
    if(ql <= mid){
        update(lc(x),l,mid,ql,qr,value);
    }
    if(qr > mid){
        update(rc(x),mid+1,r,ql,qr,value);
    }
    push_up(x);
}

  END