介绍一个python的优先队列做法。

heapq是python自带的优先队列（小根堆），其基础语法是： heapq.heappush(arr, num)

在arr里放入一个数字num，要求arr是堆。

heapq.haeppop(arr)

在arr里弹出头部的数字。

heapq本身提供的是小根堆，也就是说一个升序的数组。所以我们用其相反数来表示这个数。

我们每次拿出最湿的衣服烘干，直到最湿的衣服可以被自然风干为止。

复杂度 $O(nlogn)$ 可以通过这道题，而且比二分答案更稳更快！

import heapq

n,a,b=map(int,input().split())
c=[]
for _ in range(n):
    x = int(input())
    heapq.heappush(c, -x)

cnt=0
while c[0]<-a*cnt:
    p=heapq.heappop(c)
    p+=b
    heapq.heappush(c,p)
    cnt += 1

print(cnt)

二分+贪心

#include <bits/stdc++.h>
using namespace std;
#define Fe(i, l, r) for(int i = l; i <= r; ++ i) // 定义循环宏
const int N = 500005;

int w[N], a, b, n;
int W[N];

// 检查在x秒内是否能够将所有衣服晒干
bool check(int x){
    Fe(i, 1, n){
        W[i] = w[i];
        // 计算每件衣服减去自然晒干后剩余的湿度
        W[i] = W[i] - a * x;
    }

    int sum = 0;
    Fe(i, 1, n){
        if(W[i] <= 0) continue; // 若衣服已经干了，则跳过
        // 计算若使用烘干机则需要的时间
        sum += W[i] / b;
        if(W[i] % b) sum += 1; // 如果还有剩余湿度，需要额外的时间
        if(sum > x) return 0; // 如果所需时间超过x，则说明在x秒内无法完成晒干
    }
    return 1;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> a >> b;
    Fe(i, 1, n){
        cin >> w[i]; // 输入每件衣服的湿度
    }

    int l = 0, r = N - 2;

    // 二分查找，找到晒干所有衣服所需的最少时间
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            r = mid; // 如果可以在mid时间内晒干，尝试缩小时间
        } else {
            l = mid + 1; // 否则增加时间
        }
    }
    cout << l << endl; // 输出最少所需时间
    return 0;
}

二分答案。

def check(t):
  global clos
  global a
  global b
  res = 0
  for clo in clos:
    if (clo>t*a):
      res += (clo-t*a)//b + ((clo-t*a)%b!=0)
  # 计算每件衣服需要的烘干次数
  return res<=t # 给定的烘干次数是不是够用

n,a,b = map(int, input().split())
clos = []
ppp = 0
for _ in range(n):
  k = int(input())
  clos += [k]
  ppp = max(ppp, k)

l=1
r=ppp//a+3 

# 二分答案
while (l<r):
  mid = (l+r)>>1
  if (check(mid)):
    r = mid
  else :
    l = mid+1

print(l)

卡的很死，所以可能要两秒多，用class构了一下就过不了了。

C++好像能乱过，没写。

我有一种比较另类的做法，即开一个数组，用索引表示湿度，对应的值表示衣服数量，这样的好处是在改变索引时，往后的索引都能同时改变。

一开始想到用双端队列实现，但效率有点低，最后一个点会TE

Python (90分TE)

from collections import deque

def dryer_pop(deque: deque, b: int) -> None:
    deque[-1] -= 1
    try: 
        deque[-1 - b] += 1
    except IndexError:
        pass
    while deque and deque[-1] <= 0:
        deque.pop()

def auto_pop(deque: deque, a: int) -> None:
    for _ in range(a):
        try: 
            w_deque.popleft()
        except IndexError:
            continue

def append_to_index(deque: deque, index: int) -> None:
    for i in range(index):
        try: deque[i]
        except IndexError:
            deque.append(0)
    deque.append(1)

n: int
a: int
b: int
n, a, b = map(int, input().split())

w_deque: deque = deque()

for _ in range(n):
    w_i: int = int(input()) - 1
    try: 
        w_deque[w_i] += 1
    except IndexError:
        append_to_index(w_deque, w_i)

tot_time: int = 0

while w_deque:
    dryer_pop(w_deque, b)
    auto_pop(w_deque, a)
    tot_time += 1

print(tot_time)

后来改为窗口，效率高多了

Python (AC)

from typing import List

n: int
a: int
b: int
n, a, b = map(int, input().split())

clothes: List[int] = [0] * 1000000
L: int = 0
R: int = 0

for _ in range(n):
    w_i: int = int(input()) - 1
    clothes[w_i] += 1
    R = max(R, w_i)

tot_time: int = 0

while L <= R:
    clothes[R] -= 1
    try: clothes[R - b] += 1
    except IndexError: pass
    while L <= R and clothes[R] <= 0:
        R -= 1

    L += a
    
    tot_time += 1

print(tot_time)

既然都用数组，那我大python的字典直接申请出战

Python

n: int
a: int
b: int
n, a, b = map(int, input().split())

clothes: dict = {}  # 使用字典来存储衣服湿度信息
R: int = 0

for _ in range(n):
    w_i: int = int(input()) - 1
    clothes[w_i] = clothes.get(w_i, 0) + 1  # 更新字典中的衣服湿度信息
    R = max(R, w_i)

tot_time: int = 0

L: int = 0
while L <= R:
    if R in clothes:
        clothes[R] -= 1
        if R - b >= 0:
            clothes[R - b] = clothes.get(R - b, 0) + 1
        while L <= R and (R not in clothes or clothes[R] <= 0):  # 处理湿度为0的衣服
            R -= 1
    L += a
    tot_time += 1

print(tot_time)