挑战程序竞赛系列（16）：3.1最大化最小值
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434618
挑战程序竞赛系列（16）：3.1最大化最小值
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
花了两个月，刷完了初级篇，算入门了，心累。
POJ 3258: River Hopscotch
思路：属于二分，可以看作f(d)f(d)的一个函数，表示当前距离下，移除的石头，d越大，移除的石头也就越多。很明显是一种有序结构，所以直接在解空间中搜索满足条件的最小d即可。
static int[] rocks;
static int N;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int L = in.nextInt();
N = in.nextInt();
int M = in.nextInt();
rocks = new int[N + 2];
rocks[0] = 0;
for (int i = 1; i <= N; ++i){
rocks[i] = in.nextInt();
}
rocks[N+1] = L;
Arrays.sort(rocks);
lf = 0;
rt = L;
System.out.println(binarySearch(M));
}
static int lf;
static int rt;
public static int binarySearch(int M){
while (lf < rt){
int mid = lf + (rt - lf + 1) / 2;
if (remove(mid) > M) rt = mid - 1;
else lf = mid;
}
if (remove(lf) <= M) return lf;
return 0;
}
public static int remove(int d){
int cnt = 0;
for (int i = 1, j = 0; i <= N + 1; ++i){
if (rocks[i] - rocks[j] < d){
cnt++;
}else{
j = i;
}
}
return cnt;
}POJ 3273: Monthly Expense
思路：二分就不用说了，主要是f(m)f(m)函数，给定一个金钱范围，尽可能的塞满，问最多能塞出多少个桶。
代码如下：
static int N;
static int M;
static int[] money;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
N = in.nextInt();
M = in.nextInt();
money = new int[N];
int max = 0;
int sum = 0;
for (int i = 0; i < N; ++i){
money[i] = in.nextInt();
max = Math.max(max, money[i]);
sum += money[i];
}
int lf = max;
int rt = sum;
while (lf < rt){
int mid = lf + (rt - lf) / 2;
if (valid(mid) > M) lf = mid + 1;
else rt = mid;
}
if (valid(lf) <= M) System.out.println(lf);
else System.out.println(0);
}
public static int valid(int m){
int cnt = 0;
int sum = 0;
for (int i = 0; i < N; ++i){
sum += money[i];
if (sum == m){
sum = 0;
cnt++;
}
else if (sum > m){
sum = money[i];
cnt++;
}
}
if (sum != 0) cnt++;
return cnt;
}POJ 3104: Drying
思路：
采用模拟，专注用最优策略，每次选择最湿的衣服用散热器，其余衣服减一，用优先队列保持当前最湿。
代码如下：
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] clothes = new int[N];
MaxPQ<Integer> pq = new MaxPQ<Integer>();
for (int i = 0; i < N; ++i){
clothes[i] = in.nextInt();
pq.insert(clothes[i]);
}
int K = in.nextInt();
int cnt = 0;
while (!pq.isEmpty()){
List<Integer> tmp = new ArrayList<Integer>();
int c = pq.delMax();
c -= K;
if (c > 0) tmp.add(c);
int size = pq.size();
for (int i = 0; i < size; ++i){
c = pq.delMax();
c--;
if (c > 0) tmp.add(c);
}
for (int t : tmp) pq.insert(t);
cnt++;
}
System.out.println(cnt);
}TLE了，看来一定有数学性质来简化这过程。刚才的过程考虑了最优策略，而且程序的执行很navie，一步步走，或者你可以认为是单线程的（这也是为什么模拟慢的原因）。
所以优化的思路是能否利用一些数学性质来加快运算速度？脑子里蹦出来一个并发的概念，但必须符合并发才行啊，在哪里？此处只有一个地方有并发，每分钟自然风干时，所有的衣服都会自减一，思路就在这。而用散热器风干时，每个时刻只能操作一次，这意味着需要用散热器风干时，它就必须单独算一次。（计数是串行的）
所以优化思路是：减去所有衣服自然风干的状态（意味着模拟一下子被简化），计算剩余湿度需要散热器的次数。（而一件衣服的计数也可以在O(1)O(1)的操作内得到）
k⋅x+(mid−x)≥ai
k \cdot x + (mid - x) \ge a_i
得：
x≥⌈ai−midk−1⌉
x \ge \lceil \frac{a_i - mid}{k -1}\rceil
有趣的是，这道题如果不去假设某个mid存在，直接采用模拟很难在有限的时间内解决。而上述公式告诉我们一个事实，mid与x之间存在着映射关系，且符合有序，所以直接用二分搜索解空间就好。
代码如下：
static int[] clothes;
static int K;
static int N;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
N = in.nextInt();
clothes = new int[N];
int max = 0;
for (int i = 0; i < N; ++i){
clothes[i] = in.nextInt();
max = Math.max(max, clothes[i]);
}
K = in.nextInt();
if (K == 1){
System.out.println(max);
return;
}
int lf = 0;
int rt = max;
while (lf < rt){
int mid = lf + (rt - lf) / 2;
if (!valid(mid)) lf = mid + 1;
else rt = mid;
}
System.out.println(lf);
}
public static boolean valid(int m){
for (int i = 0, times = 0; i < N; ++i){
int more = clothes[i] - m;
if (more >= 0){
times += (int) Math.ceil(more / (1.0 * (K - 1)));
if (times > m) return false;
}
}
return true;
}POJ 3045: Cow Acrobats
和二分没什么关系。。。可以直接求解，关键是需要证明一下。每次把力量和重量总和最大的放在最下面就好了。
证明：（反证法）
假设把力量和重量总和较小的牛放在最下面，那么它的risk一定比力量和重量综合最大的risk大。
所以，我们要确保的是，放入【力重总和】最大的那头牛后，剩余的可能risk都小于较小那头的risk。
还是画个图吧。
所以我们有理由选择最大的，而不是较小的，毕竟最大的能够保证risk较小，且经后的risk都小于等于risk2，接着我们采用归纳即可，最大的选择完毕，意味着剩余的元素是个子问题，继续选择次大的即可。（隐含着选择最大后，必须选择次大元素，而非其他元素的一个过程）
代码如下：
static class Cow implements Comparable<Cow>{
int weight;
int strength;
public Cow(int weight, int strength){
this.weight = weight;
this.strength = strength;
}
@Override
public int compareTo(Cow o) {
return (o.weight + o.strength) - (this.weight + this.strength);
}
}
static Cow[] cows;
static int N;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
N = in.nextInt();
cows = new Cow[N];
long sum = 0;
for(int i = 0; i < N; ++i){
int w = in.nextInt();
int s = in.nextInt();
cows[i] = new Cow(w, s);
sum += cows[i].weight;
}
Arrays.sort(cows);
long risk = Integer.MIN_VALUE;
for (int i = 0; i < N; ++i){
sum -= cows[i].weight;
risk = Math.max(risk, sum - cows[i].strength);
}
System.out.println(risk);
}