https://ac.nowcoder.com/acm/contest/6220/C
牛牛有n件带水的衣服，干燥衣服有两种方式。
一、是用烘干机，可以每分钟烤干衣服的k滴水。
二、是自然烘干，每分钟衣服会自然烘干1滴水。
烘干机比较小，每次只能放进一件衣服。
注意，使用烘干机的时候，其他衣服仍然可以保持自然烘干状态，现在牛牛想知道最少要多少时间可以把衣服全烘干。
本来想的贪心，代码如下，
class Solution {
public:
/**
* 计算最少要多少时间可以把所有的衣服全烘干
* @param n int整型 n件衣服
* @param a int整型vector n件衣服所含水量数组
* @param k int整型 烘干机1分钟可以烘干的水量
* @return int整型
*/
int solve(int n, vector<int>& a, int k) {
// write code here
sort(a.begin() , a.end()) ;
int t = 0 ;
for(int i = a.size() - 1 ;i >= 0 ;i --) {
int res = a[i] - t ;
if(res <= 0) continue ;
res = (res / k) + (res % k ? 1 : 0) ;
t += res ;
}
return t ;
}
};
对于上述代码的贪心错误理解：
把所有的数排序一下， 然后从大到算一下时间。
我这样计算的结果就是可能存在一个x , 他x % k = y , 这个y可能是1，也可能是2，甚至别的，那么这几滴水也被用做了一分钟，何不把他自然烘干，节省时间， 将这个一分钟的时间给其他满足x >= k的来用用 ， 这样这个一分钟完全去掉了k滴水。
但是具体对两者分配不知，假设每个物品自然烘干和机器烘干的时间分别是x1 , x2 , 二分时间mid
在这个条件下，每次二分的时候，自然烘干一定是满足条件的，但是机器烘干不一定满足条件,我只需要判断机器烘干就行了
[x1 + x2 = mid
]
[a[i] = x2 * k + x1
]
[=>x2 = lceilfrac{a[i] - mid}{k - 1}
ceil
]
还要注意爆int
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <stack>
#include <set>
#pragma GCC optimize(3 , "Ofast" , "inline")
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define x first
#define y second
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair<int , int> PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
ll in()
{
ll x = 0 , f = 1 ;
char ch = getchar() ;
while(!isdigit(ch)) {if(ch == '-') f = -1 ; ch = getchar() ;}
while(isdigit(ch)) x = x * 10 + ch - 48 , ch = getchar() ;
return x * f ;
}
bool check(int n , vector<int> &a , int k , ll mid){
ll sum = 0 ;
k -- ;
if(!k) return a[n - 1] ;
for(int i = 0 ;i < n ;i ++ ) {
if(a[i] > mid) {
ll t = a[i] - mid ;
sum += t / k + (t % k ? 1 : 0) ;
}
}
return sum <= mid ;
}
int solve(int n, vector<int>& a, int k) {
// write code here
int l = 0 , r = INF ;
while(l < r) {
int mid = l + r >> 1 ;
if(check(n , a , k , mid)) r = mid ;
else l = mid + 1 ;
}
return r ;
}
int main()
{
int n = in() ;
vector<int> v(n) ;
for(int i = 0 ;i < n ;i ++) v[i] = in() ;
int k = in() ;
cout << solve(n , v , k) << endl ;
return 0 ;
}
/*
*/