【GDOI2018模拟8.14】神奇的救火现场

本文主要是介绍【GDOI2018模拟8.14】神奇的救火现场，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

输出一行表示水管的最小总长

Sample Input

3 2
12 50 81
27 73

Sample Output

23

Code

这题和一道贪心的模板题是一样的，那道题叫做保持平衡，是移树的问题
做法是，将所有的车和栓按照坐标排序，然后依次做
水管的长度是坐标之差的绝对值
因为做的时候是按照坐标依次做，所以一定是后做的坐标减前面的坐标，可以忽略绝对值
建两个堆
将自己的坐标设为x，堆顶的值为k，将累加进答案里的数为jy
对于栓，若x+k<0则会使答案更优，那么答案累加x+k并堆一中取出堆顶，jy=x+k
然后将-x-jy加入堆二中
车也类似，将两个堆对调而已
那么以后如果存在一个车的位置，它连这个栓更优，设它坐标为y，那么在做那辆车的时候，答案就会增加y-x-jy，也就是增加了水管长度并将原来不优的答案去掉了
对于车还有一点不同，就是车一定要被匹配
那么假设堆二为空，就是无法匹配了，那么jy要等于INF，答案也要加INF，那么在下一次做到栓的时候，就一定会将这辆车匹配，因为把-INF加入了堆中，-INF一定是最小的，也就是堆顶
自己理解一下吧，如果做过那道保持平衡，这题很容易理解

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(ll i=a;i<=b;i++)
#define N 101000
#define ll long long
#define INF 2147483647
using namespace std;
ll n,d[2][N*10],tot[2]={0,0},ans=0,m;
struct node{
    ll x,y;
}a[N*2];
void up(ll jy,ll x)
{
    for(;x>1&&d[jy][x]<d[jy][x/2];x/=2) swap(d[jy][x],d[jy][x/2]);
}
void down(ll jy,ll x)
{
    ll y=x*2;if(y>tot[jy]) return;
    if(y<tot[jy]&&d[jy][y+1]<d[jy][y]) y++;
    if(d[jy][y]<d[jy][x]) swap(d[jy][x],d[jy][y]),down(jy,y);
}
void ins(ll jy,ll x)
{
    d[jy][++tot[jy]]=x;up(jy,tot[jy]);
}
void del(ll jy,ll x)
{
    swap(d[jy][x],d[jy][tot[jy]]);tot[jy]--;down(jy,x);
}
bool cnt(node x,node y){return x.x<y.x;}
int main()
{freopen("fire.in","r",stdin);freopen("fire.out","w",stdout);scanf("%lld%lld",&n,&m);fo(i,1,n) scanf("%lld",&a[i]),a[i].y=1;fo(i,1,m) scanf("%lld",&a[i+n]),a[i+n].y=2;n=n+m;sort(a+1,a+n+1,cnt);fo(i,1,n){if(a[i].y==1){ll jy=0;if(tot[0]>0&&a[i].x+d[0][1]<0) jy=a[i].x+d[0][1],del(0,1);ans+=jy;ins(1,-a[i].x-jy);}else{ll jy=INF;if(tot[1]>0) jy=a[i].x+d[1][1],del(1,1);
            ans+=jy;ins(0,-a[i].x-jy);
        }
    }
    printf("%lld",ans);
}

这篇关于【GDOI2018模拟8.14】神奇的救火现场的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---