文章目錄

• Part1：題目鏈接
• Part2：題意
• Part3：思路
• • 1.在最后得到的序列中，非0數字的個數一定為k的倍數。
  • 2.對于一個數字，如果出現(xiàn)了k次以上（包含k次），那么至多只有前k次出現(xiàn)時會被涂色；否則都有可能被涂色。
• Part4：AC代碼
• Part5：整活時間

Part1：題目鏈接

點我就送新阿姆斯特朗回旋加速噴氣式阿姆斯特朗大炮[doge]

Part2：題意

現(xiàn)給出一個長度為N的數字序列，對于給出序列我們會對其中的每個數字使用k種顏料進行涂色。
涂色之后的序列需要滿足：
1.對于任意一個數字，它只能被涂上一種顏色，或是不涂色。
2.被涂上同一種顏色的數字不能出現(xiàn)重復現(xiàn)象。
3.每種顏色所上色的數字數量需相同。
4.在滿足前三者的條件下，我們希望被上色的數字越多越好。

例題：序列 [3 ，1 ，1 ，1 ，1 ，10 ，3 ，10 ，10 ，2]的上色結果：

Part3：思路

懶狗博主更新了。

昨晚的div3，由于剛跑完步累成doge，再加上期末和暑期設計，很久沒碰代碼了，打的不是很好。
這題我的思路是正確的，但是有一個參數我算錯了，導致W掉了。今天再想的時候就秒A了，昨天有點累壞了。

這題其實不難，題意很明顯，是一個貪心題。

首先我們可以從題目中得到以下幾點

1.在最后得到的序列中，非0數字的個數一定為k的倍數。

2.對于一個數字，如果出現(xiàn)了k次以上（包含k次），那么至多只有前k次出現(xiàn)時會被涂色；否則都有可能被涂色。

接下來我們需要先想出非0數字的個數究竟是k的多少倍。

其實很簡單，按照我們所說的第二條，

如果沒有規(guī)則三的限制，那么對于所有出現(xiàn)的數字，出現(xiàn)次數大于k的可以保證前k個有顏色，出現(xiàn)次數小于k的則一定都能被涂色，這時可以被涂色的數字個數設為num。

這里我們說的是沒有規(guī)則三（每種顏色所上色的數字數量需相同。）的約束下會產生的結果。

但加了規(guī)則三之后，我們需要涂色的個數就只能是k的x倍，那么x=num/k。
（我的唯一一發(fā)WA就是因為這個，嗚嗚嗚，頂不住了）

接下來貪心就可以了，就順著向下涂色，順序無所謂的。

「伊麗莎白」，放代碼！

Part4：AC代碼

#include<bits/stdc++.h> #define inf 0x3f3f3f3f3f #define pi acos(-1) using namespace std; typedef long long ll; const int maxn=2e5+100; int b[maxn]; int main() {int t;cin>>t;while(t--){int n,k,x;cin>>n>>k;map<int,vector<int> >p; //數字->數字出現(xiàn)的位置sfor(int i=0;i<n;i++){cin>>x;p[x].push_back(i);}memset(b,0,sizeof(b));map<int,vector<int> >::iterator it;int nowk=1,ans=0; //ans：記錄倍數int num=0;for(it=p.begin();it!=p.end();it++){ //篩選出有用的num，上文中有說明num+=((it->second).size()>k?k:(it->second).size());}//cout<<num<<endl;for(it=p.begin();it!=p.end();it++){int limitk=nowk-1; //思路中總結出的第2條，為了限制一個數字被涂色的次數for(int i=0;i < it->second.size();i++){b[(it->second)[i]]=nowk;nowk++;if(nowk>k) nowk=1,ans++;if(nowk==limitk+1) break;if(ans==num/k) break;}if(ans==num/k) break;}for(int i=0;i<n;i++){if(i) cout<<" ";cout<<b[i];}cout<<endl;}return 0; }

Part5：整活時間

選自《銀魂》第56話

真選組·近藤勛：
“阿通，很抱歉啊。還虧你幫我們那么多忙，但歸根到底我們就是這么一群人。
雖然想要改變，但還是一點都沒變，我們還是一群又愚蠢又粗野的，被人討厭的無能的廢物。
看來這種無能不是一朝一夕就改得了的。
但是說，就像阿通說的一樣，如果重新審視自己就會有新的發(fā)現(xiàn)。
不管我們多么被人討厭，多么受人嘲笑都沒關系。
但是決不想成為保護不了自己應該保護的東西的男人。”

總結

以上是生活随笔為你收集整理的Codeforces Round #734 (Div. 3)_B2. Wonderful Coloring - 2（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。