2025年Drying(二分)

科技前沿 • 2025-04-06 21:19 • 阅读 21

大家好，我是讯享网，很高兴认识大家。

链接：Drying

描述

现有 n 件衣服需要烘干，每件衣服的含水量为 a [ i ]．如果自然晾干，每分钟含水量减少1.如果使用烘干机烘干，每分钟含水量减少 k （直至为0）只有一台烘干机，每次只能烘干一件衣服且一次至少使用1分钟求使所有衣服含水量为 O 的最少时间是多少？

Input

输入包含三行,第一行是一个整数 n (1 <=n<=)，表示衣服的数量·第二行有 n 个整数，分别表示各件衣服的含水量 a [ i ](1< =a [ i ]<=10⁹)．第三行是一个整数 k (1<= k <=10⁹)，表示烘干机1分钟减少的水量

Output

输出只有一行，输出使所有衣服烘干的最少时间是多少？

sample input #1

3
2 3 9
5

讯享网

sample input #2

3
2 3 6
5

sample output #1

sample output #2

分析

1，看了这题，一开始我的想法是，利用k,然后计算烘干需要机器烘干的时间与k的大小进行比较，但是这样想了，却不知道怎么写，看了别人写的，他们是计算需要烘干的时间与mid作比较；
2，check函数我们假设有mid个时间可以使衣服变干，在这若干件衣服里，就有mid个时间自然烘干，mid个时间机器烘干，注意自然烘干和机器烘干是同步进行的，那么我们对于一个a[i],一开始进行a[i]-mid，就是看自然烘干是否可以，如果不可以，再进行机器烘干，机器烘干的时间就是(a[i]-mid)/(k-1),为什么是k-1，那么因为那一分钟在自然烘干那里，机器烘干自身也是需要1分钟，就相当于额外烘干k-1.但是这样可能会有小数，那么如果有余数仍需要再加一。
3，关于check函数，这题要注意向上取整，在使用机器烘干时，即使不足k个单位时间，仍然需要1分钟；
4，还有这题居然是多组测试数据，题意也没有体现出来，就是给了两组测试样例，挺坑；
5，注意数据范围；
代码实现：

#include<iostream> using namespace std; const int N=1e5+100; int q[N]; int n,k,maxa=-1; long long check(int mid) { 
    long long cnt=0;//爆int ，cnt用于统计需要多长及机器烘干时间  for(int i=1;i<=n;i++) { 
    if(q[i]>mid) { 
    int t = q[i] - mid; if(t%(k-1)!=0) cnt += t/(k-1) +1;//如果不能被整除那么就是要向上取整  else cnt += t/(k-1) ;//可以被整除  } } return cnt; } int main() { 
    while(scanf("%d",&n)!=EOF) { 
    for(int i=1;i<=n;i++) { 
    scanf("%d",&q[i]); maxa = max(maxa,q[i]);//二分的范围，最大只能是这些数中最大的  } scanf("%d",&k); if(k==1) printf("%d\n",maxa);//这里需要特判k==1的时候，否则check中会出现除0的情况  else { 
    int l=0,r=maxa; while(l<r) { 
    int mid = (l+r)/2; if(check(mid)<=mid) r=mid; else l=mid+1; } printf("%d\n",l); } } return 0; }

讯享网

总结：
1，这题对我而言还挺难的，没想出来要那么写，而且还不一定可以想到向上取整，并且多组测试数据也是没想到的，还有好多要学的地方；
2，分析题目，要注意数据范围，以及一些特殊情况；
3，附加我看到的本题几个向上取整的方法；

讯享网//第一种 cnt +=ceil(1.0*(q[i]-mid)/(k-1));//ceil向上取整，注意乘1.0,变成浮点型 //第二种 cnt += (q[i]-mid)/(k-1); if((q[i]-mid)%(k-1)) cnt++; //第三种 if((q[i]-mid)%(k-1)) cnt += (q[i]-mid)/(k-1)+1; else cnt += (q[i]-mid)/(k-1);