【題目背景】

在西西艾弗島上，生活著快樂的小 C、小 S 和小 P。最近，三位小朋友在學(xué)校里學(xué)到了“兩個數(shù)之間的距離”這一重要的概念。為了鞏固知識，小 P 玩起了“合并最近數(shù)”的游戲。

【題目描述】

A = {a1, a2, · · · ,an} 是一個包含 n 個自然數(shù)（非負(fù)整數(shù)）的集合（根據(jù)集合的定義，這 n 個數(shù)兩兩不同），且其中的最大值小于一個給定的正整數(shù) k。

小 P 需要對集合 A 中的數(shù)進(jìn)行若干輪合并操作，到 A 中僅剩一個數(shù)為止。每輪合并操作的流程如下：

選取數(shù)對 (x, y)：

• 從 A 中選取數(shù)值大小最接近的兩個數(shù) x 和 y，即 |x ? y| 在所有數(shù)對中最小；

• 如果有多個數(shù)對滿足條件，則進(jìn)一步選擇其中 (x + y) 最小的；

• 考慮到 A 中的數(shù)兩兩不同，按上述要求（即以 |x ? y| 為第一關(guān)鍵字、(x + y) 為第二關(guān)鍵字）可以選出唯一的數(shù)對 (x, y)。

將 x 和 y 合并為 z：

• z = (x + y) mod k，即將 x 和 y 求和后再對 k 取模。

• 具體來說，首先將 x 和 y 從集合 A 中刪去；如果集合 A 不包含 z，則再將 z 添加回集合 A。這保證了 A 中的自然數(shù)始終兩兩不同且小于 k。

易知，小 P 的每輪合并操作會使集合 A 的規(guī)模（即包含自然數(shù)的個數(shù)）減少 1 或 2。你需要幫小 P 搞明白，在全部合并操作結(jié)束后，進(jìn)行的合并操作的總輪數(shù)和 A 中剩下的那個數(shù)。

【輸入格式】

從標(biāo)準(zhǔn)輸入讀入數(shù)據(jù)。

輸入的第一行包含用空格分隔的兩個正整數(shù) n 和 k。

輸入的第二行包含 n 個用空格分隔的自然數(shù) a1, a2, · · · , an。

【輸出格式】

輸出到標(biāo)準(zhǔn)輸出。

輸出共兩行。

第一行輸出一個整數(shù) T，表示總共進(jìn)行了 T 輪合并操作。

第二行輸出 T 輪合并操作后 A 中剩下的那個數(shù)。

【樣例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

【子任務(wù)】

40% 的測試數(shù)據(jù)滿足 n ≤ 200、k ≤ 1000；

70% 的測試數(shù)據(jù)滿足 n ≤ 2000、k ≤ 10^5；

全部的測試數(shù)據(jù)滿足 n ≤ 10^5、k ≤ 10^8，輸入的 ai（1 ≤ i ≤ n）兩兩不同且0 ≤ ai < k。

【思路】

這題70分的數(shù)據(jù)為n≤2000，先使用set保存值，保證有序性，兩個for每次找相鄰最小的差值，從set里刪除這兩個數(shù)并將和加到set里，這樣又保證了唯一性，直到set的size為1就可以輸出答案，期間需要每次刪除并添加值的時候記錄次數(shù)。

既然能想到set里找相鄰最小差值為什么不一開始就去維護(hù)最小差值呢？使用優(yōu)先隊(duì)列去維護(hù)就不需要使用一個for去找，將一個for的O(n)減少到O(1)，這樣整體的O(n)對于100分的n≤10^5不就滿足了。

【題解】

首先將所有元素放入set保證每次序列的有序性和唯一性，后面也可以判斷使用的值是否已經(jīng)被刪掉了，然后將set里的值前后兩兩值（這里記為x，y）和差值（這里記為dif）放入一個優(yōu)先隊(duì)列中，這里的優(yōu)先隊(duì)列是以dif為第一優(yōu)先級，dif小的先出隊(duì)列，x+y為第二優(yōu)先級，x+y小的先出隊(duì)列。每次取出隊(duì)列中的頭元素，首先要判斷取出的元素兩個值是否還存在與set，保證兩個值都還未被刪掉，刪掉了這兩個數(shù)的差值就沒有意義了，直接continue，否則就算一個操作，操作次數(shù)+1，然后將兩個值從set里刪掉，并且判斷兩個數(shù)的和是否存在于set里，若存在就不需要加進(jìn)去了，否則將這個和加進(jìn)去并且需要在set定位這個值，維護(hù)其前后的差值加到優(yōu)先隊(duì)列里，保證了在更新刪除時不會出錯，這樣一直從set里每次減少一個值，直到set存的值剩下一個數(shù)便可退出，輸出操作次數(shù)并輸出set里剩下的那一個數(shù)。

以上說的和都是在取模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 %d\n",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("%d\n%d\n",ans,*st.begin());return 0; }

總結(jié)

以上是生活随笔為你收集整理的2021CCSP最近数合并的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。