# 挑战程序竞赛系列（16）：3.1最大化最小值

## POJ 3258: River Hopscotch

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

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;
int size = pq.size();
for (int i = 0; i < size; ++i){
c = pq.delMax();
c--;
}
for (int t : tmp) pq.insert(t);
cnt++;
}
System.out.println(cnt);
}

TLE了，看来一定有数学性质来简化这过程。刚才的过程考虑了最优策略，而且程序的执行很navie，一步步走，或者你可以认为是单线程的（这也是为什么模拟慢的原因）。

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

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

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);
}

0 条评论

• ### 挑战程序竞赛系列（26）：3.5二分图匹配（1）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（21）：3.2反转

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（19）：3.1最小化第k大的值

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 杭电1003--动态规划

思路：用数组a[]记录序列中的数，对于a[i]只有两种可能 1.为一个序列的首2.为一个序列的尾。 用数组b[i]记录以第i个数结尾的序列的最大和，则 b[...

• ### HDU 1867（kmp应用）

Generally speaking, there are a lot of problems about strings processing. Now yo...

• ### 1062. 最简分数(20)

一个分数一般写成两个整数相除的形式：N/M，其中M不为0。最简分数是指分子和分母没有公约数的分数表示形式。

• ### Top K问题

如果你对上述两者的原理有所了解,可以继续往下看.如果不了解,可以点击链接先看一下基础~.

• ### E - Explorer

给你 n 个点，m 条边，每条边给你一组数 (u, v, l, r) 代表如果你想从u点走到v点，你的身高需要满足范围 [ l , r ] ，问你从 1 走到...

• ### BZOJ2705: [SDOI2012]Longge的问题(欧拉函数)

$$ans = \sum_{d | n} d \phi(\frac{n}{d})$$