期末复习之二分

1.Aggressive cows

描述
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,…,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don’t like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
输入

• Line 1: Two space-separated integers: N and C

• Lines 2…N+1: Line i+1 contains an integer stall location, xi
  输出

• Line 1: One integer: the largest minimum distance
  样例输入
  5 3
  1
  2
  8
  4
  9
  样例输出
  3
  提示
  OUTPUT DETAILS:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.

Huge input data,scanf is recommended.
思路：简单的二分法加上一个判断是否可行的函数
注意每次mid可行时，用它更新ans的值，最后的mid可能是不成立的，所以不能输出mid

#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int dis[100001] = {};
bool legal(int d){int cnt = 1;int last = dis[0];for(int i = 1; i < n; ++i){if(dis[i] - last >= d){++cnt;last = dis[i];}if(cnt == m)return 1;}return 0;
}
int main()
{cin >> n >> m;int ans = 0;for(int i = 0; i < n; i++)cin >> dis[i];sort(dis, dis+n);int R = 1, L = dis[n-1]/m;int mid = 0;while(R <= L){mid = R + (L-R)/2;if(legal(mid)){R = mid + 1;ans = mid;}elseL = mid - 1;}cout << ans << endl;return 0;
}

2.网线主管

描述
仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成，他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起，即将它们全部连到一个单一的中心服务器。为了组织这个完全公正的比赛，裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。

为购买网线，裁判委员会联系了当地的一个网络解决方案提供商，要求能够提供一定数量的等长网线。裁判委员会希望网线越长越好，这样选手们之间的距离可以尽可能远一些。

该公司的网线主管承接了这个任务。他知道库存中每条网线的长度（精确到厘米），并且只要告诉他所需的网线长度（精确到厘米），他都能够完成对网线的切割工作。但是，这次，所需的网线长度并不知道，这让网线主管不知所措。

你需要编写一个程序，帮助网线主管确定一个最长的网线长度，并且按此长度对库存中的网线进行切割，能够得到指定数量的网线。

输入
第一行包含两个整数N和K，以单个空格隔开。N（1 <= N <= 10000）是库存中的网线数，K（1 <= K <= 10000）是需要的网线数量。
接下来N行，每行一个数，为库存中每条网线的长度（单位：米）。所有网线的长度至少1m，至多100km。输入中的所有长度都精确到厘米，即保留到小数点后两位。
输出
网线主管能够从库存的网线中切出指定数量的网线的最长长度（单位：米）。必须精确到厘米，即保留到小数点后两位。
若无法得到长度至少为1cm的指定数量的网线，则必须输出“0.00”（不包含引号）。
样例输入
4 11
8.02
7.43
4.57
5.39
样例输出
2.00
(法一）double数组直接做，错误。存疑

#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
const double EXP = 0.00000001;
double l[10010] = {};
bool legal(double num){int cnt = 0;for(int i = 0; i < n; ++i){cnt += int(l[i]/num);if(cnt >= m)return 1;}return 0;
}
int main()
{cin >> n >> m;double sum = 0;for(int i = 0; i < n; ++i){cin >> l[i];sum += l[i];}sort(l ,l + n);double R = l[n-1]/m, L = sum/m;double ans = 0;while(L - R > EXP){double mid = R + (L-R)/2;if(legal(mid)){ans = mid;R = mid;}elseL = mid;}printf("%.2lf\n", (ans < 0.01?0:ans));return 0;
}

（法二）统一x100转成int来做，正确

#include <bits/stdc++.h>
using namespace std;
int n,k,l=0,r=1e7;
double tmp;
int a[10010];
int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%lf",&tmp),a[i]=ceil(tmp*100);//ceil向上取整while(l<r) {int mid=(l+r+1)/2;int rec=0;for(int i=1;i<=n;i++) rec+=a[i]/mid;if(rec>=k) l=mid;else r=mid-1;}printf("%.2lf",l/100.00);return 0;
}

2.矩形分割

描述
平面上有一个大矩形，其左下角坐标（0，0），右上角坐标（R,R)。大矩形内部包含一些小矩形，小矩形都平行于坐标轴且互不重叠。所有矩形的顶点都是整点。要求画一根平行于y轴的直线x=k（k是整数) ，使得这些小矩形落在直线左边的面积必须大于等于落在右边的面积，且两边面积之差最小。并且，要使得大矩形在直线左边的的面积尽可能大。注意：若直线穿过一个小矩形，将会把它切成两个部分，分属左右两侧。

输入
第一行是整数R，表示大矩形的右上角坐标是(R,R) (1 <= R <= 1,000,000)。
接下来的一行是整数N,表示一共有N个小矩形(0 < N <= 10000)。
再接下来有N 行。每行有4个整数，L,T, W 和 H, 表示有一个小矩形的左上角坐标是(L,T),宽度是W，高度是H (0<=L,T <= R, 0 < W,H <= R). 小矩形不会有位于大矩形之外的部分。
输出
输出整数n，表示答案应该是直线 x=n。 如果必要的话，x=R也可以是答案。
样例输入
1000
2
1 1 2 1
5 1 2 1
样例输出
5
思路：对最后的++j部分存疑

#include <iostream>
using namespace std;
long long map[1000050] = {},all=0,a[1000050] = {};
int s, n, x, y, w, h, L, R, D, ans;
int main()
{cin >> s >> n;for (long long i = 0; i < n; i++){cin >> x >> y >> w >> h;for (long long i = x; i < x + w; i++){all += h;map[i] += h;}}a[0] = map[0];for (long long i = 1; i < s; i++){a[i] = a[i - 1] + map[i];}L = 0;R = s;D = L + (R - L) / 2;ans = s - 1;while (D != L){D = L + (R - L) / 2;if (a[D] >= all - a[D]){R = D - 1;ans = D;}else{L = D + 1;}}long long j;for (j = ans; a[j] == a[ans] && j < s; j++);cout << j << endl;
}