藍橋杯 ALGO-135 Multithreading
標簽: 藍橋杯算法訓練
題意:假設有一組線程去執行一個函數,上面也提到了,thr[i]的意思是:i表示是第i個線程,thr[i]表示需要此線程執行該任務多少次,執行的函數里面包含兩句話,所以thr[i]執行的總數為thr[i]*2, 函數的表示的意思是:第一個是鎖存住Y的值,第二個把鎖存住的值進行+1。此題有點類似于多線程的問題,由于未進行同步,所以當完執行第一句話的時候,其他的線程也可能也在執行此函數,也保存了相應的Y值,然后當執行該線程執行第二句的時候,對鎖存住的Y值進行+1。在這樣的情況下求出其所需要求解的值,當然也可能存在多個線程或者一個線程執行此函數的問題。求在這樣的情況下能否得到其所需的值。
參考大佬的:https://blog.csdn.net/huangxinfeng_/article/details/50780367
代碼:
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct{
int i,xi;
}ST;
void display1(ST &thr){//執行一次某個線程并將其xi-1
cout<<thr.i<<" ";
thr.xi--;
}
void display2(ST *thr,int st,int en) {//按順序執行完st-en的線程數
for(int i=st;i<=en;i++)
for(int j=0;j<thr[i].xi;j++)
cout<<thr[i].i<<" ";
}
bool com(ST a,ST b){return a.xi<b.xi;}
int main(){
ST thr[101],temp;
int n,w,max=0,i,j;
cin>>n>>w;
w*=2; //w擴大兩倍方便計算
for(i=1;i<=n;i++){//讀取數據保存在結構體中 保存線程下標i以及執行次數val
cin>>thr[i].xi;
thr[i].xi*=2; //乘以2 因為循環一次要執行兩次i
thr[i].i=i; //保存線程號
max+=thr[i].xi; //統計所能計算的最大數
}
sort(thr+1,thr+n+1,com); //按照線程執行次數從小到大排序
if(w>=1&&w<=max){
if(n==1){//當n=1是一種特殊情況要分開討論
if(w==max){
cout<<"Yes"<<endl;
display2(thr,1,1);
}
else cout<<"No";
}else{
if(w<=thr[1].xi){//這里有兩種情況如果w<最小線程執行次數的話要用后一個線程來消磨最小線程從而得到更小的Y值
if(w==thr[1].xi&&w==2){//因為消磨最小也要執行兩次所以當w=1(本身擴大兩倍)也是一種特殊情況
cout<<"Yes"<<endl;
display1(thr[1]);//消磨了一次之后,thr==1,
display2(thr,2,n);//中間不管怎么消磨,最后會消磨一次1,達到最后的結果
display1(thr[1]);//消磨完畢,thr==0
}else if(w>2){
cout<<"Yes"<<endl;
display1(thr[2]);//執行一次線程2用于保存Y值方便消磨一次線程1
j = thr[1].xi-w+2;//要加個2因為后面消磨之后會剩下一個1,后面還會消磨一個thr2
while(j--){
display1(thr[1]);//消磨掉多余的執行次數
}
display1(thr[2]);//因為只執行過一次thr2所以xi=y=0 這里再執行一次則y=xi+1 所以不管上面怎么運行,運行完這句之后y=1上面運行值被重置
display1(thr[1]);//再執行一次thr1則將Xi的值重置為第二次運行的值xi=y=1這就是為什么要多消磨一次的原因了
display2(thr,2,n);//按順序顯示i-n剩余的線程數
display2(thr,1,1);
}else cout<<"No";
}else{
cout<<"Yes"<<endl;
max=0;
for(i=1;i<=n;i++){
max+=thr[i].xi;
if(w<max)break;
}
if(i>n){//i>n的話說明剛好所以都包括,直接輸出
display2(thr,1,n);
}else{
display1(thr[1]);//相當于初始化Y=0
j=max-w;//最后一個線程未執行的次數
while(j--){
display1(thr[i]);
}
display2(thr,i+1,n);
display2(thr,1,i);
}
}
}
}else {
cout<<"No";
}
return 0;
}
智能推薦
藍橋杯 ALGO-81 動態數組使用
題意:對數組進行處理,刪除0后返回剩余不為0的個數。 思路:使用vector做,然后函數使用引用,vector刪除之后,后面元素會自動像前面移動,引用保證函數對原始的vector修改 代碼: ...
藍橋杯 ALGO-53 最小乘積(基本型)
題意:給定n組測試數據,然后輸入一組數據的數量,然后求這兩組數據的最小乘積和。 思路:把數據整體考慮,不用分正負號,一個按從小到大排序,一個按從大到小排序,從頭開始是一個最大的乘以一個最小的,把所有的乘積加起來便得到的最小的乘積和。 代碼: ...
猜你喜歡
freemarker + ItextRender 根據模板生成PDF文件
1. 制作模板 2. 獲取模板,并將所獲取的數據加載生成html文件 2. 生成PDF文件 其中由兩個地方需要注意,都是關于獲取文件路徑的問題,由于項目部署的時候是打包成jar包形式,所以在開發過程中時直接安照傳統的獲取方法沒有一點文件,但是當打包后部署,總是出錯。于是參考網上文章,先將文件讀出來到項目的臨時目錄下,然后再按正常方式加載該臨時文件; 還有一個問題至今沒有解決,就是關于生成PDF文件...
電腦空間不夠了?教你一個小秒招快速清理 Docker 占用的磁盤空間!
Docker 很占用空間,每當我們運行容器、拉取鏡像、部署應用、構建自己的鏡像時,我們的磁盤空間會被大量占用。 如果你也被這個問題所困擾,咱們就一起看一下 Docker 是如何使用磁盤空間的,以及如何回收。 docker 占用的空間可以通過下面的命令查看: TYPE 列出了docker 使用磁盤的 4 種類型: Images:所有鏡像占用的空間,包括拉取下來的鏡像,和本地構建的。 Con...
requests實現全自動PPT模板
http://www.1ppt.com/moban/ 可以免費的下載PPT模板,當然如果要人工一個個下,還是挺麻煩的,我們可以利用requests輕松下載 訪問這個主頁,我們可以看到下面的樣式 點每一個PPT模板的圖片,我們可以進入到詳細的信息頁面,翻到下面,我們可以看到對應的下載地址 點擊這個下載的按鈕,我們便可以下載對應的PPT壓縮包 那我們就開始做吧 首先,查看網頁的源代碼,我們可以看到每一...
Linux C系統編程-線程互斥鎖(四)
互斥鎖 互斥鎖也是屬于線程之間處理同步互斥方式,有上鎖/解鎖兩種狀態。 互斥鎖函數接口 1)初始化互斥鎖 pthread_mutex_init() man 3 pthread_mutex_init (找不到的情況下首先 sudo apt-get install glibc-doc sudo apt-get install manpages-posix-dev) 動態初始化 int pthread_...