字节--房间分配
字節(jié)–房間分配
文章目錄
- 字節(jié)--房間分配
- 一、問題描述
- 二、分析
- 三、代碼
一、問題描述
有n個房間，現(xiàn)在i號房間里的人需要被重新分配，分配的規(guī)則是這樣的：先讓i號房間里的人全都出來，接下來按照 i+1, i+2, i+3, ... 的順序依此往這些房間里放一個人，n號房間的的下一個房間是1號房間，直到所有的人都被重新分配。
現(xiàn)在告訴你分配完后每個房間的人數(shù)以及最后一個人被分配的房間號x，你需要求出分配前每個房間的人數(shù)。數(shù)據(jù)保證一定有解，若有多解輸出任意一個解。
- 輸入描述:
- 輸出描述:
二、分析
- 來解釋一下，題目里面的i是某一個房間i，我們不知道是那個具體的房間i，并不是所有房間都要重新分配，只是i房間重新分配.
初始情況：
4 4 4
現(xiàn)在第3房間的人重新分配
(為了與語言一致,即使得房間編號從0開始,代碼中會認(rèn)為是2號房間
4 4 0
1 1 1
1
最終結(jié)果為
6 5 1
- 題目本身不涉及什么算法，純模擬。
- 第一種想法是，從最后一個分配房間逆推，每個房間減一個人，直到遇到某個房間人數(shù)減為0。
- 這個過程所減的總?cè)藬?shù)就是i號房間的人數(shù)，其它房間也變?yōu)槠鹗既藬?shù)。按照這個想法編碼，case率80%，超時。
- 第二種想法是找到分配房間i的位置，再根據(jù)i房間當(dāng)中的人數(shù)來還愿所有房間的人數(shù)
- 如下圖中所示：
- 首先我們假設(shè)這個數(shù)組中人數(shù)最少的房間就是起始房間分配后的結(jié)果（就是問題當(dāng)中的i房間）。因?yàn)槊恳淮畏峙浣o其他所有房間1個人之后才給它自己分配1個人，所以最少人數(shù)的房間才有可能是i號房間。
- 如果發(fā)現(xiàn)有多個相同的最小值，那么就以終止房間x遞減到第一個對應(yīng)的最小值為準(zhǔn)。
因?yàn)槿绻霈F(xiàn)2個或者2個以上的最小值相等的情況，那么就說明i房間當(dāng)中的人數(shù)無法分配一圈，一旦i房間中的人數(shù)可以分配一圈，那么i房間的人數(shù)增加1，其他所有房間都增加1，不可能出現(xiàn)相等的情況，所以如果出現(xiàn)多個相同的最小值的時候以終止房間x遞減到第一個對應(yīng)的最小值為準(zhǔn)
- 上述對應(yīng)圖中標(biāo)紅部分，我們可以順著推，從起始房間i開始分配，最后i的值為min_val，那么也就是說每個房間都至少加了min_val個數(shù)（因?yàn)榉峙鋾r是從下一個開始的，i房間的人數(shù)都分配到min_val個，那么其他房間肯定至少有min_val個）。
- 最后終止于房間x也即是說從起始房間向右轉(zhuǎn)一圈到x又增加了1，即是圖中標(biāo)紅的部分增加了min_val+1，藍(lán)色部分則是表明只增加了min_val，相當(dāng)于最后一圈并沒有轉(zhuǎn)完，只轉(zhuǎn)到x位置就停止了。
- 此時我們再看起始節(jié)點(diǎn)，根據(jù)計算的話應(yīng)該是上述增加的和，合并起來其實(shí)就是=min_valn+d，因?yàn)槊總€都分配了min_val個，紅色部分長度為d，每個多加1，所以增加1d的數(shù)量即可。
三、代碼
#include <bits/stdc++.h> using namespace std; int main() { int n ; int x ; cin>>n>>x; //數(shù)組，存放每個房間分配完成后的人數(shù)long* person_now = new long[n];//保存數(shù)組中最少的人數(shù)，用來確定那個房間的人數(shù)被分配出去，即題目中的i房間 long min_value = INT_MAX; for(int i = 0; i < n; i++) { cin>>person_now[i]; min_value = min(min_value, person_now[i]); } //題目中的房間號是從1開始的，所以-1int index = x - 1; //用來保存沒有轉(zhuǎn)完一圈剩下的房間數(shù)，即x到i房間的距離，圖中的dint count = 0; //開始，(index + n) % n的原因是index是不斷減小的，因?yàn)樵诜峙鋓房間人數(shù)時是以//i,i + 1,....,n,1,2,...i這種順序的，所以我們是反著來還原的，即//index,index - 1,....1,0,n,n - 1,....index,所以是為了防止越界訪問//!= min_value目的有兩個：//1.因?yàn)槲覀兪且詉ndex遞減的順序遍歷的，那么第一個和min_val值相等的房間//剛好就是題目中的i號房間，也就是把人數(shù)拿出來分配的房間，避免了相同的min_val//情況；//2.從index遞減到第一個等于min_val房間之間的所有房間一定是至少分配了//min_val + 1個人，也就是圖中的紅色部分，+ 1就是紅色部分比藍(lán)色部分//多走的半圈while(person_now[(index + n) % n] != min_value) { //還原紅色部分的原始房間person_now[(index + n) % n] -= min_value + 1; //遞減index下標(biāo)index--; count++; } //還原第i號房間的原始人數(shù)，就是最少房間的人數(shù)person_now[(index + n) % n] = min_value * n + count;index--;//還原圖中的藍(lán)色部分的原始人數(shù)，就是只分配了min_val個人數(shù)，最后沒走完//一圈剩下的房間數(shù)while((index + n) % n != x - 1) {person_now[(index + n) % n] -= min_value;index--;}//打印結(jié)果for(int i = 0; i < n; i++) {cout<<person_now[i]<<" ";}return 0; }總結(jié)
