题解 AT1757 【花火】

· · 题解

弃了好久的题，时隔良久又翻出来，终于像是有了思路

我们贪心的想

如果没有不能向后走的限制的话

我们每次都到烟花的释放点，有多个释放点就取中间点

这是非常好想的

但是如果加上这个限制呢？

局部贪心就不是最优解了

考虑不加限制时的过程，当ニワンゴくん向后走时，

如果这并不是实际最优解，即ニワンゴくん当前这步走的比最优解多

我们就将这步拉回来，并重新计算贡献

具体怎么实现呢？代码可能写的有点奇怪

就拿样例说吧，

5 10
1 2
1 4
3 8
4 7
5 1

我们按时间倒着排序，来避免对后面造成的影响

首先，站在原点不动的代价是\sum_{i=1}^np_i=22

第一个是 5 1

当前在零位置，到1位置，代价是1，但是我们可以挪到1位置，这样代价就是1-1=0

第二个是 4 7

当前在1位置,本来只可以向前挪，这里回溯到7位置，代价是7-1=6，

第三个是 3 8

当前在7位置向前，到8位置需要回溯，代价最少是8-7=1，

第四个是 1 4

当前在8位置向前，回到4不需要代价

第五个是 1 2

因为时间与第四个是一致的，代价一定是2，可以写作4-2

总代价为0+6+1+0+2=9

思考我们的过程，回到之前的不需要代价，向后需要的代价为其坐标的绝对值

所以可以直接把当前的p_i压入优先队列，取出最小的p做就好了，

这里之所以压入两次是为了去掉之前\sum_{i=1}^np_i的影响

#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<set>
#include<queue>
#define int long long
using namespace std;
inline int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch))f|=ch=='-',ch=getchar();
    while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}
typedef pair<int,int> pairs;
priority_queue<int> q;
multiset<pairs> v;
signed main(){
    int n=read(),sum=0,ans=0;read();
    while(n--){
        int t=read(),p=read();
        v.insert(make_pair(-t,p));
        sum+=p;
    }
    for(multiset<pairs>::iterator it=v.begin();it!=v.end();it++){
        q.push(-(*it).second),q.push(-(*it).second);
        ans+=q.top(),q.pop();
    }
    printf("%lld\n",ans+sum);
    return 0;
}