2021CCSP最近数合并

62 阅读 0 评论 41 点赞

我是靠谱客的博主小巧饼干，最近开发中收集的这篇文章主要介绍2021CCSP最近数合并，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【题目背景】

在西西艾弗岛上，生活着快乐的小 C、小 S 和小 P。最近，三位小朋友在学校里学到了“两个数之间的距离”这一重要的概念。为了巩固知识，小 P 玩起了“合并最近数”的游戏。

【题目描述】

A = {a1, a2, · · · ,an} 是一个包含 n 个自然数（非负整数）的集合（根据集合的定义，这 n 个数两两不同），且其中的最大值小于一个给定的正整数 k。

小 P 需要对集合 A 中的数进行若干轮合并操作，到 A 中仅剩一个数为止。每轮合并操作的流程如下：

选取数对 (x, y)：

从 A 中选取数值大小最接近的两个数 x 和 y，即 |x − y| 在所有数对中最小；
如果有多个数对满足条件，则进一步选择其中 (x + y) 最小的；
考虑到 A 中的数两两不同，按上述要求（即以 |x − y| 为第一关键字、(x + y) 为第二关键字）可以选出唯一的数对 (x, y)。

将 x 和 y 合并为 z：

z = (x + y) mod k，即将 x 和 y 求和后再对 k 取模。
具体来说，首先将 x 和 y 从集合 A 中删去；如果集合 A 不包含 z，则再将 z 添加回集合 A。这保证了 A 中的自然数始终两两不同且小于 k。

易知，小 P 的每轮合并操作会使集合 A 的规模（即包含自然数的个数）减少 1 或 2。你需要帮小 P 搞明白，在全部合并操作结束后，进行的合并操作的总轮数和 A 中剩下的那个数。

【输入格式】

从标准输入读入数据。

输入的第一行包含用空格分隔的两个正整数 n 和 k。

输入的第二行包含 n 个用空格分隔的自然数 a1, a2, · · · , an。

【输出格式】

输出到标准输出。

输出共两行。

第一行输出一个整数 T，表示总共进行了 T 轮合并操作。

第二行输出 T 轮合并操作后 A 中剩下的那个数。

【样例1输入】

9 10

0 1 2 3 4 5 6 7 8 9

【样例1输出】

7

5

【样例1解释】

第一轮：(0,1) → 1，合并后 A = {1, 2, 4, 5, 6, 7, 8, 9}；

第二轮：(1, 2) → 3，合并后 A = {3, 4, 5, 6, 7, 8, 9}；

第三轮：(3, 4) → 7，合并后 A = {5, 6, 7, 8, 9}；

第四轮：(5, 6) → 1，合并后 A = {1, 7, 8, 9}；

第五轮：(7, 8) → 5，合并后 A = {1, 5, 9}；

第六轮：(1, 5) → 6，合并后 A = {6, 9}；

第七轮：(6, 9) → 5，合并后 A = {5}。

【样例2输入】

6 11

7 3 6 5 10 0

【样例2输出】

4

9

【子任务】

40% 的测试数据满足 n ≤ 200、k ≤ 1000；

70% 的测试数据满足 n ≤ 2000、k ≤ 10^5；

全部的测试数据满足 n ≤ 10^5、k ≤ 10^8，输入的 ai（1 ≤ i ≤ n）两两不同且0 ≤ ai < k。

【思路】

这题70分的数据为n≤2000，先使用set保存值，保证有序性，两个for每次找相邻最小的差值，从set里删除这两个数并将和加到set里，这样又保证了唯一性，直到set的size为1就可以输出答案，期间需要每次删除并添加值的时候记录次数。

既然能想到set里找相邻最小差值为什么不一开始就去维护最小差值呢？使用优先队列去维护就不需要使用一个for去找，将一个for的O(n)减少到O(1)，这样整体的O(n)对于100分的n≤10^5不就满足了。

【题解】

首先将所有元素放入set保证每次序列的有序性和唯一性，后面也可以判断使用的值是否已经被删掉了，然后将set里的值前后两两值（这里记为x，y）和差值（这里记为dif）放入一个优先队列中，这里的优先队列是以dif为第一优先级，dif小的先出队列，x+y为第二优先级，x+y小的先出队列。每次取出队列中的头元素，首先要判断取出的元素两个值是否还存在与set，保证两个值都还未被删掉，删掉了这两个数的差值就没有意义了，直接continue，否则就算一个操作，操作次数+1，然后将两个值从set里删掉，并且判断两个数的和是否存在于set里，若存在就不需要加进去了，否则将这个和加进去并且需要在set定位这个值，维护其前后的差值加到优先队列里，保证了在更新删除时不会出错，这样一直从set里每次减少一个值，直到set存的值剩下一个数便可退出，输出操作次数并输出set里剩下的那一个数。

以上说的和都是在取模k之上的。

#include <bits/stdc++.h>
using namespace std;
int n,k,x;
struct node{
    int x,y,dif;
    node(int _x,int _y,int _dif):x(_x),y(_y),dif(_dif){}
    bool operator < (const node &t)const{
        if(t.dif!=dif)return dif>t.dif;
        return x+y>t.x+t.y;
    }
};
int main(){
    scanf("%d%d",&n,&k);
    set<int>st;
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        st.insert(x);
    }
    int ans=0;
    priority_queue<node>q;
    for(auto it=st.begin();;it++){
        it++;
        if(it==st.end())break;
        auto nex=it;
        it--;
        q.emplace(node(*it,*nex,*nex-*it));
    }
    while(st.size()!=1){
        node now=q.top();q.pop();
        if(st.find(now.x)==st.end()||st.find(now.y)==st.end())continue;
        ans++;
        auto k1=st.find(now.x);
        auto k2=st.find(now.y);
        k2++;
        if(k1!=st.begin()&&k2!=st.end()){
            k1--;
            q.emplace(node(*k1,*k2,*k2-*k1));
        }
        st.erase(now.x);
        st.erase(now.y);
        //printf("%d %dn",now.x,now.y);
        int val=(now.x+now.y)%k;
        //for(auto v:st){
        //    cout<<v<<' ';
        //}
        //cout<<'n';
        if(st.find(val)==st.end()){
            st.insert(val);
            //for(auto v:st){
             //   cout<<v<<' ';
            //}
            //cout<<'n';
            auto it=st.find(val);
            if(it!=st.begin()){
                it--;
                auto pre=it;
                it++;
                q.emplace(node(*pre,*it,*it-*pre));
            }
            it++;
            auto suf=it;
            it--;
            if(suf!=st.end()){
                q.emplace(node(*it,*suf,*suf-*it));
            }
        }
    }
    printf("%dn%dn",ans,*st.begin());
    return 0; 
}