題意:假設有一組線程去執行一個函數,上面也提到了,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;
}