6 条题解

  • 7
    @ 2024-5-31 20:16:11

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

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

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

    heapq.haeppop(arr)

    在arr里弹出头部的数字。

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

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

    复杂度 O(nlogn)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)
    
    • @ 2024-6-1 7:39:49

      逆天大顶堆 未曾设想的道路

  • 4
    @ 2024-5-27 16:51:16

    二分+贪心

    #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;
    }
    
    • 2
      @ 2024-5-29 19:42:19

      二分答案。

      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++好像能乱过,没写。

      • 1
        @ 2025-5-24 4:39:29

        因为python一直超时所以找到了这个来输入每件衣服的湿度

        import sys
        
        w = list(map(int, sys.stdin.read().split()))
        
        

        可以大幅缩短输入时间

        • 0
          @ 2024-6-1 7:43:49

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

          一开始想到用双端队列实现,但效率有点低,最后一个点会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)
          
          • -2
            @ 2024-6-2 15:26:49

            既然都用数组,那我大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)
            
            • 1

            信息

            ID
            936
            时间
            3000ms
            内存
            256MiB
            难度
            9
            标签
            递交数
            576
            已通过
            38
            上传者