ICPC Northeastern European Regional Contest 2019 Apprentice Learning Trajectory

题意：

有n个时间段可以铸剑，每个时间段都有不同的工作效率（即铸一把剑所需的时间）。

铸剑开始后只有这把剑完成后才能去下一把

问最多可以铸多少把剑

有一道经典贪心题 线段覆盖

区间上有若干个线段，选取不重叠的最多的线段

做法是按右端点排序，贪心选取

这道题如果把每个时间段都分解成若干个长为工作效率的区间

做法如同上题

但显然会超时

这样相当于对每个时间点进行考虑

实际上只需要考虑每个时间段的开始时间和结束时间

因为换时间段只会出现在某个时间段的开始或结尾

不会出现从A换到B，B还可以有贡献，又换回了A

每个时间段（l,r,t）抽取2个时间点,l+t 和 r

从小到大排序

以这2n个点将区间划分为新的区间

然后枚举的过程中，维护一个小根堆结构

每次都用从当前时间开始，能够铸剑最快的那个点的单位时间

可用的总时间是从当前时间到枚举到的这个点的时间（l+t或者r）

如果枚举到l+t的点，把点加入堆中

如果枚举到r的点，将对应的l+t的点从堆中删除

为什么先计算贡献，再插点？

因为枚举到的每个点表示要计算从当前时间到枚举的点的时间的贡献

如果枚举的点的时间是l+t，当前这个点的单位铸剑时间t又最短

那么目前为止这个点会有1的贡献，这个1的贡献让前面的时间段加上也不影响结果

（不会表达了）

为什么是l+t呢？

一个是因为假设第一个点是一个l=1，但t非常大的点。

先计算从当前时间点到枚举的点的时间 这一时间段 的贡献

将他放入堆后，下一个点将用这个产生贡献，显然是不优的

再一个原因就是上面那个了

#include<cstdio>
#include<set>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 200001

typedef long long LL;

struct node
{
    LL st,t;
    bool tag;
}a[N<<1];

multiset<LL>s;

bool cmp(node p,node q)
{
    if(p.st!=q.st) return p.st<q.st;
    return p.tag>q.tag;
}

int main()
{
    int n,m=0;
    scanf("%d",&n);
    LL l,r,tt;
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld%lld",&l,&r,&tt);
        a[++m].st=l+tt;
        a[m].t=tt;
        a[m].tag=1;
        a[++m].st=r;
        a[m].t=tt;
        a[m].tag=0;
    }
    sort(a+1,a+m+1,cmp);
    LL ans=0,now=0,num;
    for(int i=1;i<=m;++i)
    {
        if(!s.empty())
        {
            num=(a[i].st-now)/(*s.begin());
            ans+=num;
            now+=num*(*s.begin()); 
        }
        if(a[i].tag)
        {
            if(now<=a[i].st-a[i].t)
            {
                now=a[i].st;
                ans++;
            }
            s.insert(a[i].t);
        }
        else s.erase(s.find(a[i].t));
    }
    cout<<ans;
}