147. 数据备份(优先队列+模拟链表)

古城微笑少年丶 2021-11-14 12:34 252阅读 0赞

题目链接：[https://www.acwing.com/problem/content/149/][https_www.acwing.com_problem_content_149]

分析：根据题意，我们是要选择k对城市出来，并且k对城市之间的距离之和要最小。  
如果3号城市和四号城市为一对了。那么三号城市就不能和2号城市凑成一对。  
所以，我们可以把每个城市之间的距离算出来。从中选择最小的距离。但是需要注意，不一定是选择最小的，还有可能是选择最小两边的那两对。  
所以  
选择了D\[i\],那么D\[i-1\]和D\[i+1\]都不能选择了  
选择了D\[i+1\]和D\[i-1\],然后无法选择D\[i\].  
那么我们可以先选择D\[i\]。然后把D\[i + 1\] 和 D\[i - 1\] 从序列中删除。把D\[i\] 的值更新为  
D\[i + 1\] + D\[i - 1\] - D\[i\];

#include"stdio.h"
    #include"string.h"
    #include"queue"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    typedef pair<ll,int> PLL;
    int n,k;
    ll a[100100];
    int l[100100],r[100100];
    ll dis[100100];
    priority_queue< PLL ,vector<PLL>,greater<PLL> > Q;
    int del[100100];
    
    int main()
    {
        scanf("%d%d",&n,&k);
        for(int i = 1; i <= n; i ++)
            {
                scanf("%lld",&a[i]);
                l[i] = i - 1; r[i] = i + 1;
            }
        for(int i = 2; i <= n; i ++)
            {
              dis[i - 1] = a[i] - a[i - 1];
              Q.push({dis[i - 1],i - 1});
            }
        l[0] = -1; r[0] = 1; l[n] = n - 1; r[n] = n + 1;
        dis[0] = 1e15; dis[n] = 1e15;
        //Q.push({dis[1],1}); Q.push({dis[n+1],n + 1});
        ll sum = 0;
        while(k --)
        {
            PLL T = Q.top(); Q.pop();
            while(del[T.second])
            {
                T = Q.top(); Q.pop();
            }
            del[l[T.second]] = 1; del[r[T.second]] = 1;
            sum += T.first;
            Q.push({dis[l[T.second]] + dis[r[T.second]] - dis[T.second],T.second});
            dis[T.second] = dis[l[T.second]] + dis[r[T.second]] - dis[T.second];
            l[T.second] = l[l[T.second]];
            r[l[T.second]] = T.second;
            r[T.second] = r[r[T.second]];
            l[r[T.second]] = T.second;
        }
        printf("%lld\n",sum);
    }
    
    /*
    #include"stdio.h"
    #include"string.h"
    #include"set"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    typedef pair<ll,int> PLL;
    
    int n,k;
    ll a[100100];
    int l[100100],r[100100];
    ll dis[100100];
    set< PLL > Q;
    
    int main()
    {
        scanf("%d%d",&n,&k);
        for(int i = 1; i <= n; i ++)
            scanf("%lld",&a[i]);
        for(int i = 1; i < n; i ++)
        {
            dis[i] = a[i + 1] - a[i];
            l[i] = i - 1; r[i] = i + 1;
            Q.insert({dis[i],i});
        }
        l[0] = -1; r[0] = 1; l[n] = n - 1; r[n] = n + 1;
        dis[0] = 1e15; dis[n] = 1e15;
        ll sum = 0;
        while(k --)
        {
            auto T = Q.begin();
            sum += T->first;
            int left = l[T->second];
            int right = r[T->second];
            Q.erase(T);
            Q.insert({dis[left] + dis[right] - dis[T->second],T->second});
            dis[T->second] = dis[left] + dis[right] - dis[T->second];
            Q.erase({dis[left],left});
            Q.erase({dis[right],right});
            
            r[l[left]] = r[left];
            l[r[left]] = l[left];
            r[l[right]] = r[right];
            l[r[right]] = l[right];
        }
        printf("%lld\n",sum);
    }*/

[https_www.acwing.com_problem_content_149]: https://www.acwing.com/problem/content/149/