#16769: 根據 K 的情況決定解法


rollfc (胖胖貓)

School : 國立交通大學
ID : 81012
IP address : [111.249.73.72]
Last Login :
2022-08-16 11:01:43
c296. APCS-2016-1029-3定時K彈 -- 2016年10月APCS | From: [115.82.65.219] | Post Date : 2019-02-06 04:21

原本的測資加入了最後一筆導致單純使用 vector.erase() 模擬移除淘汰掉的號碼出現 TLE

這時候需要回歸到剩餘人數的情況,當剩餘人數過多時當然還是維持使用 vector 模擬過程即可

但是當剩餘人數過少時就需要『動態規劃』找出剩下的號碼,做法類似 uva-1452 的經典問題

加上找出第 K 次時淘汰的號碼在哪個位置後輸出下一個合法位置上的號碼。

這邊為了確認想法是否合乎出題者,用 Try & Error 方式拿到後台測資實際上是不合規定的,先跟出題者說聲抱歉還請見諒

 
#17868: Re:根據 K 的情況決定解法


p3a_owhj (阿普二信)

School : No School
ID : 39897
IP address : [114.35.246.70]
Last Login :
2022-08-07 22:24:24
c296. APCS-2016-1029-3定時K彈 -- 2016年10月APCS | From: [218.161.13.235] | Post Date : 2019-05-26 23:15

 

 

 



辛苦了,互相交流才會進步,需要測資或提示可以寄站內信給我哦。

 
#18747: Re:根據 K 的情況決定解法


grorge (中正最廢coder)

School : 臺北市立中正高級中學
ID : 67868
IP address : [140.114.206.92]
Last Login :
2022-03-04 23:44:11
c296. APCS-2016-1029-3定時K彈 -- 2016年10月APCS | From: [220.136.52.21] | Post Date : 2019-08-03 22:57

黑暗作法是使用#include<ext/rope>的rope就可以用vector模擬的方法AC了

 
#19141: Re:根據 K 的情況決定解法


089487 (089487)

School : 國立臺灣師範大學附屬高級中學
ID : 82069
IP address : [114.45.205.138]
Last Login :
2022-07-30 23:04:03
c296. APCS-2016-1029-3定時K彈 -- 2016年10月APCS | From: [223.137.219.26] | Post Date : 2019-09-05 19:57

黑暗作法是使用#include<ext/rope>的rope就可以用vector模擬的方法AC了

用#include<ext/rope>的rope

#include<iostream>

#include<algorithm>

#include <ext/rope>

//#include <x86intrin.h>

using namespace std;

using namespace __gnu_cxx;

int main() {

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t,k,m,j=0,length;

cin>>t>>m>>k;

rope<int> v;

for(int i=0;i<t;i++) v.push_back(i+1);

while(k--)

{

j+=m-1;

if(j>=v.size()) j%=v.size();

v.erase(j,1); 

//for(int ii=0;ii<v.size();ii++) cout<<v[ii]<<" ";

//cout<<endl;

}

if(j>=v.size()) j-=v.size();

cout<<v[j]<<endl;

  return 0;

}

 

AC (0.6s, 6.5MB)
 
ZeroJudge Forum