挑战程序竞赛系列（19）：3.1最小化第k大的值
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434626
挑战程序竞赛系列（19）：3.1最小化第k大的值
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
- POJ 2010: Moo University - Financial Aid
- POJ 3662: Telephone Lines
- POJ 1759: Garland
- POJ 3484: Showstopper
POJ 2010: Moo University - Financial Aid
思路：
针对区间的二分头一次见，不过很有意思，总的思想是，给定了一个mid值之后，统计左区间符合total的个数left和右区间的个数right，如果left较小，说明mid不够大，更新lb，而左右区间个数均符合的情况下，更新lb，因为总是求较大的mid。
package com.daimens.algorithm.june;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
public class SolutionDay26_P2010 {
InputStream is;
PrintWriter out;
String INPUT = "./data/judge/2010.txt";
class Cow {
int rank;
int score;
int aid;
@Override
public String toString() {
return "[" + score + ", " + aid + "]";
}
}
void solve() {
int N = ni();
int C = ni();
int F = ni();
Cow[] scores = new Cow[C];
Cow[] aids = new Cow[C];
for (int i = 0; i < C; ++i) {
int score = ni();
int aid = ni();
scores[i] = new Cow();
scores[i].aid = aid;
scores[i].score = score;
}
Arrays.sort(scores, new Comparator<Cow>() {
@Override
public int compare(Cow o1, Cow o2) {
return o1.score - o2.score;
}
});
for (int i = 0; i < C; ++i) {
scores[i].rank = i;
}
aids = Arrays.copyOf(scores, scores.length);
Arrays.sort(aids, new Comparator<Cow>() {
@Override
public int compare(Cow o1, Cow o2) {
return o1.aid - o2.aid;
}
});
int lb = 0, ub = C, ans = -1;
while (ub - lb > 1) {
int mid = lb + (ub - lb) / 2;
int total = scores[mid].aid;
int left = 0, right = 0;
for (int i = 0; i < C; ++i) {
if (aids[i].rank < mid && total + aids[i].aid <= F && left < N / 2) {
total += aids[i].aid;
left++;
} else if (aids[i].rank > mid && total + aids[i].aid <= F && right < N / 2) {
total += aids[i].aid;
right++;
}
}
if (left < N / 2 && right < N / 2) {
ans = -1;
break;
} else if (left < N / 2) {
lb = mid;
} else if (right < N / 2) {
ub = mid;
} else { // 满足条件的尽可能让mid变大
ans = scores[mid].score;
lb = mid;
}
}
out.println(ans);
}
void run() throws Exception {
is = oj ? System.in : new FileInputStream(new File(INPUT));
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}
public static void main(String[] args) throws Exception {
new SolutionDay26_P2010().run();
}
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte() {
if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
lenbuf = is.read(inbuf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}
private double nd() {
return Double.parseDouble(ns());
}
private char nc() {
return (char) skip();
}
private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}
private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private int ni() {
int num = 0, b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
private void tr(Object... o) {
if (!oj)
System.out.println(Arrays.deepToString(o));
}
}POJ 3662:Telephone Lines
好题，结合了DIJKSTRA和二分搜索解空间，且问题的求解思路也很有趣。
思路：
此题关键不在于求cost的最短路径，需要转换一下，假设我们知道符合条件的mid值，要让mid尽可能的小，这就意味着大于mid的边连接到N的边数要尽量少，这跟我们的二分判断有关系，假设mid = 0的情况下，意味着FJ不需要付任何费用，那么剩余的路径中必须满足<=K的条件，那么FJ当然是尽可能的选择抵达农场N的最小边数咯，所以问题就转换成了边数的求解，而非cost，所以构造边的时候，用int newEdge = (edge.cost > mid ? 1 : 0) + dist[edge.from];来构造。
FJ的策略：
- mid值给定，选择抵达N结点边数最小的路径，二分是为了进一步降低mid的边界。
- 如果最短边数都超过了K，说明在这种mid下是不可能存在这种解的，lb = mid + 1；
DIJKSTRA的细节就不再论述了，可以参考http://blog.csdn.net/u014688145/article/details/73350943#t4
代码如下：
public class SolutionDay26_P3662 {
InputStream is;
PrintWriter out;
String INPUT = "./data/judge/3662.txt";
class Edge{
int from;
int to;
int cost;
public Edge(int from, int to, int cost){
this.from = from;
this.to = to;
this.cost = cost;
}
@Override
public String toString() {
return "Edge [from=" + from + ", to=" + to + ", cost=" + cost + "]";
}
}
class Node implements Comparable<Node>{
int id;
int cost;
public Node(int id, int cost){
this.id = id;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return this.cost - o.cost;
}
}
int[] dist;
int INF = 1 << 29;
void solve() {
int N = ni();
int P = ni();
int K = ni();
dist = new int[N];
List<Edge>[] graph = new ArrayList[N];
for (int i = 0; i < N; ++i) graph[i] = new ArrayList<Edge>();
int max = 0;
for (int i = 0; i < P; ++i){
int from = ni();
int to = ni();
int cost = ni();
max = Math.max(max, cost);
from--;
to--;
graph[from].add(new Edge(from, to, cost));
graph[to].add(new Edge(to, from, cost));
}
int lb = 0, ub = max;
while (lb < ub){
int mid = lb + (ub - lb) / 2;
if (dijkstra(graph, 0, mid) > K) lb = mid + 1;
else ub = mid;
}
if (dijkstra(graph, 0, lb) <= K) out.println(lb);
else out.println(-1);
}
public int dijkstra(List<Edge>[] graph, int i, int mid){
int N = graph.length;
boolean[] visited = new boolean[N];
Queue<Node> queue = new PriorityQueue<Node>();
Arrays.fill(dist, INF);
dist[i] = 0;
queue.offer(new Node(i, dist[i]));
while (!queue.isEmpty()){
Node min = queue.poll();
if (visited[min.id]) continue;
visited[min.id] = true;
for (Edge edge : graph[min.id]){
int newEdge = (edge.cost > mid ? 1 : 0) + dist[edge.from];
if (newEdge <= dist[edge.to]){
dist[edge.to] = newEdge;
queue.offer(new Node(edge.to, dist[edge.to]));
}
}
}
return dist[N-1];
}
void run() throws Exception {
is = oj ? System.in : new FileInputStream(new File(INPUT));
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}
public static void main(String[] args) throws Exception {
new SolutionDay26_P3662().run();
}
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte() {
if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
lenbuf = is.read(inbuf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}
private double nd() {
return Double.parseDouble(ns());
}
private char nc() {
return (char) skip();
}
private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}
private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private int ni() {
int num = 0, b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
private void tr(Object... o) {
if (!oj)
System.out.println(Arrays.deepToString(o));
}
}POJ 1759: Garland
思路：
求B的最低值，所以假设B值存在即可，但如果从B点求，很难求出其他点，且公式告诉我们，知道连续的两个点，任意一个点的高度都能求出。所以与其求B还不如转去求h1h_1的高度。为了让B尽可能的低，让h1h_1尽可能的靠近h0h_0即可。
代码如下：
public class SolutionDay26_P1759 {
InputStream is;
PrintWriter out;
String INPUT = "./data/judge/1759.txt";
double[] h;
void solve() {
int N = ni();
h = new double[N];
double A = nd();
h[0] = A;
double lf = 0, rt = A + 16;
for (int i = 0; i < 100; ++i){
double mid = (lf + rt) / 2;
if (valid(mid, N)) rt = mid;
else lf = mid;
}
out.printf("%.2f\n",B);
}
double B = 0.0;
boolean valid(double mid, int N){
h[1] = mid;
for (int i = 2; i < N; ++i){
h[i] = 2 * h[i-1] + 2 - h[i-2];
if (h[i] < 0) return false;
}
B = h[N-1];
return true;
}
void run() throws Exception {
is = oj ? System.in : new FileInputStream(new File(INPUT));
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}
public static void main(String[] args) throws Exception {
new SolutionDay26_P1759().run();
}
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte() {
if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
lenbuf = is.read(inbuf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}
private double nd() {
return Double.parseDouble(ns());
}
private char nc() {
return (char) skip();
}
private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}
private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private int ni() {
int num = 0, b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
b = readByte();
}
while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
b = readByte();
}
}
private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
private void tr(Object... o) {
if (!oj)
System.out.println(Arrays.deepToString(o));
}
}POJ 3484: Showstopper
这题没有通过，不知道哪里出了问题，非常无语。此题的核心在于：
出现奇数次的数是唯一的，这就意味着其他数出现的次数都为偶数，利用这个性质，可以二分。
给定一个可能的存在奇数次的数，那么每个等差数列的项数总和为偶数，说明该数还在更大的地方，否则在更小的地方。
代码如下：
public class SolutionDay26_P3484 {
static int MAX_CASE = 1000000;
static long[] X = new long[MAX_CASE];
static long[] Y = new long[MAX_CASE];
static long[] Z = new long[MAX_CASE];
static long[] C = new long[MAX_CASE];
static int N = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
String line = in.nextLine();
if (!line.equals("")){
String[] nums = line.trim().split(" ");
X[N] = Long.parseLong(nums[0]);
Y[N] = Long.parseLong(nums[1]);
Z[N] = Long.parseLong(nums[2]);
N++;
}
else{
if (N == 0){
continue;
}
long lst_bit = 0;
for (int i = 0; i < N; ++i){
C[i] = (Y[i] - X[i]) / Z[i] + 1;
lst_bit ^= C[i];
}
if ((lst_bit & 1) == 0){
System.out.println("no corruption");
}
else{
long lf = 0, rt = Long.MAX_VALUE;
while (lf < rt){
long mid = lf + (rt - lf) / 2;
if ((valid(mid) & 1) == 0) lf = mid + 1;
else rt = mid;
}
System.out.println(lf + " " + (valid(lf) - valid(lf -1)));
}
N = 0;
clear();
}
}
in.close();
}
public static void clear(){
X = new long[MAX_CASE];
Y = new long[MAX_CASE];
Z = new long[MAX_CASE];
C = new long[MAX_CASE];
}
public static long valid(long mid){
long sum = 0;
for (int i = 0; i < N; ++i){
if (mid >= Y[i]) sum += C[i];
else if (mid >= X[i]){
sum += (mid - X[i]) / Z[i] + 1;
}
}
return sum;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017年06月26日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
