NOIP2012模擬試題【奶牛曬衣服】，noip2012模擬試題
1．奶牛曬衣服(dry)
【問題描述】
在熊大媽英明的帶領下，時針和它的同伴生下了許多牛寶寶。熊大媽決定給每個寶寶都穿上可愛的嬰兒裝。於是，為牛寶寶洗曬衣服就成了很不爽的事情。
聖人王擔負起了這個重任。洗完衣服後，你就要弄干衣服。衣服在自然條件下用1的時間可以曬干A點濕度。摳門的熊大媽買了1台烘衣機。使用烘衣機可以讓你用1的時間使1件衣服除開自然曬干的A點濕度外，還可烘干B點濕度，但在1的時間內只能對1件衣服使用。
N件的衣服因為種種原因而不一樣濕，現在告訴你每件衣服的濕度，要你求出弄干所有衣服的最少時間（濕度為0為干）。
【輸入】
第一行N，A，B；接下來N行，每行一個數，表示衣服的濕度(1≤濕度，A，B≤500000，1≤N≤500000)。
【輸出】
一行，最少時間。
【樣例】
dry.in
3 2 1
1
2
3
dry.out
1
【樣例解析】
第1個時間內，用機器處理第3件衣服，此外，所有衣服自然曬干2。花費1時間全部弄干。
剛拿到題的時候以為是dp，TAT因為一大早就和和另一個妹子在看容斥原理，滿腦子都是dp（/手動再見，我就是這麼蠢）
後來才知道是非！常！簡！單！的一個隊列題！啊啊啊啊啊啊啊啊l(っ*´Д`)っ！
（為啥我這麼蠢啊！）
因為隨著時間的增加，只要沒有晾干的衣服都會進行濕度-a的操作，所以我們可以直接用一個變量sum來記錄總共要減去的濕度，就不需要每次都把每件衣服都減去a了
下面的代碼有足夠的注釋=v=不再多說
![]()
1 #include<cstdio>
2 #include<cstring>
3 #include<queue> //***
4 #include<algorithm>
5 using namespace std;
6 priority_queue<int>q;//***
7 int n,a,b;
8 int w;
9 void read()
10 {
11 scanf("%d%d%d",&n,&a,&b);
12 int w;
13 for(int i=1;i<=n;i++)
14 {
15 scanf("%d",&w);
16 q.push(w);//將濕度入隊；
17 }
18 int sum=0;
19 int t=0;
20 while(!q.empty())//如果隊列不為空，即還有衣服沒晾干；
21 {
22 int k=q.top();
23 if(k<=sum){
24 printf("%d",t);
25 return;
26 }//如果無需烘干，即當前的自然曬干的濕度的總和>衣服的濕度，直接打印；
27 else{//需要烘干機；
28 q.pop();
29 k-=b;//烘干機操作後的濕度；
30 sum+=a;//自然曬干的濕度的總和等於這一次操作之前適度的總和加這一次的曬干的濕度；
31 t++;//時間加一；
32 q.push(k);//將k再次入隊判斷（因為k還沒有晾干所以還需要更多的時間）
33 }
34 }
35 printf("%d",t);
36 }
37 int main()
38 {
39 freopen("dry.in","r",stdin);
40 freopen("dry.out","w",stdout);
41 read();
42 }
隊列
