这题几个小坑,调了很久才出来:
1.注意k是吹风机和自然烘干的共同结果!减去1后才是吹风机的单独作用!
2.需要对边界k==1特判
思路不会太难:本题相当于求晾干最长时间的最小值,可以考虑二分解决。若用时间x能晾干,则>x也能晾干,接下来只需考虑<x的部分。若用时x晾不干,则>x也不能晾干。
二分的最终答案是使judge(mid)==1成立的最后一个mid,而跳出36行的while循环时,必有r+1==l,即r刚好跑到l左边。由于每次judge判断成立时r=mid-1,因此最终答案=mid=r+1=l
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> using namespace std; typedef long long ll; ll a[100010]; int n; ll k; bool judge(ll x){ ll cnt=0;//使用吹风机次数 for(int i=0;i<n;i++){ if(a[i]>x){ ll tmp=ceil(1.0*(a[i]-x)/k);//记录每件衣服需要使用的吹风机次数 cnt+=tmp; } if(cnt>x) return false;//使用吹风机的次数多于x了,就无法实现 } return true; } int main(){ //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); scanf("%d",&n); ll l=0,r=-1; for(int i=0;i<n;i++){ scanf("%lld",&a[i]); r="max(r,a[i]);" } scanf("%lld",&k); k-="1;" if(k="=0){" printf("%lld\n",r); return 0; while(l<="r){" ll mid="(l+r)">>1; if(judge(mid)) r=mid-1; else l=mid+1; } printf("%lld\n",l);//也可写成printf("%lld\n",r+1); return 0; }