1.假定一个解判断是否可行
POJ 1064
#include <iostream>
#include <vector>
#define INF 10000
using namespace std;
int N, K;
vector<double> ropes;
bool C(double x) {
int num = 0;
for (int i = 0; i < N; i++) {
num += (int)(ropes[i] / x);
}
return num >= K;
}
void slove() {
double lb = 0, ub = INF;
for (int i = 0; i < 100; i++) {
double mid = (lb + ub) / 2;
if (C(mid))
lb = mid;
else
ub = mid;
}
printf_s("%.2f\n", floor(ub * 100) / 100);
}
int main()
{
cin >> N >> K;
double length;
for (int i = 0; i < N; i++) {
cin >> length;
ropes.push_back(length);
}
slove();
return 0;
}
二分法的结束判定：
在输出小数的问题中，一般会指定输出中小数点后面的位数，所以有必要设置合理的结束条件来控制精度，上面的题中达到了的精度范围，也可以设置类似ub-lb>EPS这样的条件。
2.最大化最小值（二分+贪心）
POJ 2456
Ｎ间小屋，Ｍ头牛，使得牛跟牛之间的距离最远，以防止牛打架。
#include <iostream>
#include <algorithm>
#include <cstdio>
#define MAX_N 100001
#define INF 20000
using namespace std;
int N, M;
int x[MAX_N];
bool C(int d) {
int last = 0;
for (int i = 1; i < M; i++) {
int crt = last + 1;
while (crt<N&&x[crt]-x[last]<d)
{
crt++;
}
if (crt == N) {
return false;
}
last = crt;
}
return true;
}
void solve() {
int lb = 0, ub = INF;
while (ub - lb > 1) {
int mid = (lb + ub) / 2;
if (C(mid)) {
lb = mid;
}
else {
ub = mid;
}
}
printf("%d\n", lb);
}
int main()
{
scanf("%d %d", &N, &M);
for (int i = 0; i < N; ++i) {
scanf("%d", &x[i]);
}
sort(x, x + N );
solve();
return 0;
}
不断缩小可用值的范围，选取最大的值，贪心法+二分法
POJ 3258
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#define Max_N 50000
using namespace std;
int L, N, M;
vector<int> stones(Max_N);
bool C(int mid) {
int last = 0;
for (int i = 1; i < N +2 - M; ++i) {
int current = last + 1;
while (current<N+2&&stones[current]-stones[last]<mid)
{
++current;
}
if (current == N+2) {
return false;
}
last = current;
}
return true;
}
void solve() {
sort(stones.begin(), stones.begin() + N+2);
int lb = 0, ub = L+1;
while (ub - lb > 1) {
int mid = (ub + lb) / 2;
if (C(mid)) {
lb = mid;
}
else {
ub = mid;
}
}
printf("%d\n", lb);
}
int main()
{
scanf("%d %d %d", &L, &N, &M);
for (int i = 1; i <= N; i++) {
scanf("%d", &stones[i]);
}
stones[0] = 0;
stones[N+1] = L;
solve();
return 0;
}
POJ 3273
#include <iostream>
#include <cstdio>
#define Max_N 100000
using namespace std;
int Days[Max_N];
int N, M;
bool C(int mid) {
int pig = 0;
int t = 0;
for (int i = 0; i < N; ) {
t++;
while ((i<N)&&(pig + Days[i] <= mid)) {
pig += Days[i];
i++;
}
pig = 0;
if (t > M ) {
return false;
}
}
return true;
}
void solve() {
int lb = 0, ub = 50000;
while (ub - lb > 1) {
int mid = (ub + lb) / 2;
if (C(mid)) {
ub = mid;
}
else {
lb = mid;
}
}
printf("%d\n", ub);
}
int main()
{
scanf("%d %d", &N, &M);
for (int i = 0; i < N; ++i) {
scanf("%d", &Days[i]);
}
solve();
return 0;
}
POJ 3104
#include <iostream>
#define Max_N 10000000
#define INF 1000000000
using namespace std;
int n, k;
int a[Max_N];
//mid为时间
bool C(long long mid) {
int wind = 0;
for (int i = 0; i < n; ++i) {
if (a[i] > mid) {
int t = 0;
do {
t++;
wind++;
} while (mid+t*(k-1)<a[i]&&(wind<=mid));
if (wind > mid)
return false;
}
}
return true;
}
void solve() {
long long lb = 1, ub = INF;
while (ub - lb > 1) {
long long mid = (ub + lb) / 2;
if (C(mid)) {
ub = mid;
}
else {
lb = mid;
}
}
cout << ub << endl;
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
cin >> k;
solve();
return 0;
}
3.最大化平均值
有n个物品的重量和价值分别是和
。从中选出k个物品使单位重量的价值最大。
#include <iostream>
#include <algorithm>
#include <cstdio>
#define Max_N 1000000
#define INF 10010
using namespace std;
int n, k;
int w[Max_N], v[Max_N];
double y[Max_N];//v-x*w
bool C(double x) {
for (int i = 0; i < n; ++i) {
y[i] = v[i] - w[i] * x;
}
sort(y, y + n);
double sum = 0;
//计算从大到小k个数的和，若差小于0，则平均值不成立
for (int i = 0; i < k; i++) {
sum += y[n - i - 1];
}
return sum >= 0;
}
void solve() {
double lb = 0, ub = INF;
for (int i = 0; i < 100; i++) {
double mid = (lb + ub) / 2;
if (C(mid))
lb = mid;
else
ub = mid;
}
printf("%.2f\n", ub);
}
int main()
{
scanf("%d %d", &n, &k);
for (int i = 0; i < n; ++i) {
scanf("%d %d", &w[i], &v[i]);
}
solve();
return 0;
}
一般先想到对物品按照单位价值排序，但是根据样例，这是不可行的。
解决方法变为，其中x为最大的平均单位价值，化简得
，因此对这个式子的值进行贪心的由大到小选取k个。
网友评论