三分/01分数规划

🔗 引用站外地址，请注意甄别
第四课：三分/01分数规划
517coding

A：点到线段的距离

🔗 引用站外地址，请注意甄别
点到线段的距离
517coding

三分

通过观察可以发现，点 $P$ 到线段 $AB$ 的距离呈 “U” 字形

接下来只用再这个 “U” 字形种寻找最小的点即可

首先设最左边的端点为 $l$ ，最右边的端点为 $r$

第一次滑动到三分之一和三分之二位置，设三分之一位置为 $mid1$ ，三分之二位置为 $mid2$

假如 $mid1<mid2$ ，就说明 $mid2$ 到 $r$ 不会存在最小值，这样每次就会变少三分之一

相反，如果 $mid2<mid2$，就说明 $l$ 到 $mid1$ 不会存在最小值

要使得答案始终都在 $mid1$ 和 $mid2$ 之间，这样等到它们足够接近时，就可以找到答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-8;

struct point {
    double x, y, z;
};

point A, B, P;

//计算三维坐标中两点的距离
double dis(point a, point b) {
    double tmp1 = b.x - a.x;
    double tmp2 = b.y - a.y;
    double tmp3 = b.z - a.z;
    return sqrt(tmp1 * tmp1 + tmp2 * tmp2 + tmp3 * tmp3);
}
//根据比例算出P点到s点的距离
double get(double mid) {
    point s;
    s.x = A.x + (B.x - A.x) * mid;
    s.y = A.y + (B.y - A.y) * mid;
    s.z = A.z + (B.z - A.z) * mid;
    return dis(s, P);
}
int main() {
    int T;
    cin >> T;
    while(T--) {
        cin >> A.x >> A.y >> A.z;
        cin >> B.x >> B.y >> B.z;
        cin >> P.x >> P.y >> P.z;
        //三分AS：SB的比值
        double l = 0, r = 1, best = -1;
        while(fabs(r - l) > eps) {
            double mid1 = l + (r - l) / 3;
            double mid2 = r - (r - l) / 3;
            best = get(mid1);//记录答案
            if (get(mid1) - get(mid2) < -eps) r = mid2;
            else l = mid1;
        }
        printf("%.2f\n", best);
    }
    return 0;
}

B：三角形与四边形

🔗 引用站外地址，请注意甄别
三角形与四边形
517coding

算法：浮点二分

假设 AD 的长度为 $x$ ，那么 $DB$ 的长度为 $AB-x$，那么就可以得到三角形和四边形的面积比

紧接着，我们发现 $x$ 越大，三角形和四边形的比值也会越大，这样就发现这道题题目具备单调性，可以二分

因为比值涉及浮点数，所以要用浮点二分

值得注意的是二分的上界，经过计算， $x$ 最终的结果不会超过 $AB$ （因为 $x$ 是从 $AB$ 上截取的线段）

关于三角形已知三条边求面积

可以直接用公式

先算出周长的一半 $p = (a+b+c)/2$，其中 $a,b,c$ 分别为三角形的三条边

然后面积 $S = \sqrt{p(p-a)(p-b)(p-c)}$

也可以直接输出AB/sqrt((k+1)/k)

注意 eps 的精度！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-10;
double ab, ac, bc, k;

//已知三角形三条边求面积
double calc(double a, double b, double c) {
    double p = (a + b + c) / 2;
    return sqrt(p * (p - a) * (p - b) * (p - c));
}
bool check(double x) {
    double ad = x;
    double ae = ac * ad / ab;
    double de = ad * bc / ab;
    double ans = calc(ad, ae, de) / (calc(ab, ac, bc) - calc(ad, ae, de));
    return ans - k > -eps;
}
int main() {
    int T, ca = 1;
    scanf("%d", &T);
    while(T--) {
        scanf("%lf%lf%lf%lf", &ab, &ac, &bc, &k);
        double l = 0, r = ab, best = -1;
        while(fabs(r - l) > eps) {
            double mid = (l + r) / 2;
            //check(mid)如果返回true表示AD=mid的时候面积比>=k
            if (check(mid)) best = mid, r = mid;//注意这里l,r不用+1或-1
            else l = mid;
        }
        printf("Case %d: %.2f\n", ca++, best);
    }
    return 0;
}

C：最大比例

🔗 引用站外地址，请注意甄别
最大比例
517coding

转化

注意：以下的 $v_1,v_2,v_3…v_k$ 和 $w_1,w_2,w_3+…w_k$ 都代表的是从原数组中任意的 $k$ 个数

解： $\frac{v_1+v_2+v_3+…+v_k}{w_1+w_2+w_3+…+w_k}=ans$

两边同时乘上 $w_i+w_2+w_3+…w_k$ ，得

$v_1+v_2+v_3+…+v_k=ans(w_1+w_2+w_3+…w_k)$

把 $ans$ 乘进 $(w_1+w_2+w_3+…w_l)$，得

$v_1+v_2+v_3+…v_k=ans·w_1+ans·w_2+ans·w_3+…+ans·w_k$

移项，得

$(v1-ans·w_1)+(v_2-ans·w_2)+(v_3-ans·w_3)+…+(v_k-ans·w_k)=0$

其中 $ans$ 相当于选出 $k$ 个数的比例

设 $a_i=v_i-ans·w_i$

就可以设出一个平直角坐标系的纵坐标（ $y$ 轴）为最大的 $k$ 个 $a_i$ 的和（即前 $k$ 大的 $a_i$ 的和）

单调性

当 $ans$ （比例）越大的时候，前 $k$ 大的数会越小

需要求的就是 $ans$ 尽量的大，但同时使得 $a_1+a_2+a_3+…+a_k$ 大于等于 $0$

知道了单调性以后，二分比值即可，然后去找 $a_i$ 中较大的 $k$ 个 $0$ 进行 check

当 $ans$ 最大的时候，$a_1+a_2+a_3+…+a_k=0$，这就是最终的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
 
const int N = 100010;
const double INF = 1000010;
const double eps = 1e-8;

int n, k;
struct node {
    int id;
    int v, w;
    double x;
    //计算式子中的每一个“a[i]”
    void calc(double tmp) {
        x = v - tmp * w;
    }
    //重载运算符
    bool operator < (const node& cmp) const {
        return x > cmp.x;
    }
} a[N];
 
//判断式子是否大于等于0
bool check(double x) {
    for (int i = 1; i <= n; i++) a[i].calc(x);
    sort(a + 1, a + n + 1);
    double tmp = 0;
    for (int i = 1; i <= k; i++) tmp += a[i].x;
    return tmp >= 0;
}
 
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].v, &a[i].w);
        a[i].id = i;//记录编号，防止排序影响结果
    }
    //二分比值
    double l = 0, r = INF;
    while(fabs(r - l) > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    for (int i = 1; i <= k; i++) {
        printf("%d ", a[i].id);
    }
    return 0;
}

D：后缀零

🔗 引用站外地址，请注意甄别
后缀零
517coding

算法：整数二分

题意：找到一个最小的 $n$ ，使得 $n!$ 末尾一共有 $Q$ 个 $0$ （$Q \le 10^8$）

怎样求 $n!$ 末尾有多少个0

$n!$ 末尾有几个 $0$ ，要怎么算呢？

举个栗子，比如说 $25!$

$25!=1\times2\times3\times4\times5\times……\times23\times24\times25$

末尾的 $0$ 是怎么得到的呢？

是 $5$ 的个数，因为 $2\times5=10$ ，能够产生一个 $0$，其他的所有的末尾的 $0$ 都是这么得来的

一个数的阶乘末尾的 $0$ 怎么得来的呢？

其实就是阶乘中相乘的数包含的 $5$ 的个数

$25!$ 中包含 $5$ 的数有 $5,10,15,20,25$

其中包含一个 $5$ 的数有 $5,10,15,20$

包含两个 $5$ 的数有 $25$

总结以下这道题目的方法：求 $n!$ 末尾有几个 $0$ 本质上就是求 $\frac{n}{5}+\frac{n}{5^2}+……\frac{n}{5^k}$ ，一直到加的数小于 $1$ 为止

单调性

一个数的阶乘末尾的 $0$ 的个数是具备单调性的，这个数越大，末尾的 $0$ 越多，所以可以二分

二分的上界

二分很重要的依据就是二分的上界，那么这道题目二分的上界应该是多少呢？

$Q$ 大概有 $10^8$，所以我们需要知道多少的阶乘末尾有 $10^8$ 个 $0$ 

1
2
3
4
5
6
7
8
int get(int n) {
    int ans = 0;
    while(n > 0) {
        ans += n / 5;
        n /= 5;
    }
    return ans;
}

get 函数用来获取一个数的阶乘末尾 $0$ 的个数，如果输出 get (1e9)，输出的结果很明显大于 $10^8$，所以可以得到二分的上界应当为 $10^9$ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

const int INF = (int) 1e9;//二分上界

//求n！末尾有几个0，效率为O(logn)
int get(int n) {
    int ans = 0;
    while(n > 0) {
        ans += n / 5;
        n /= 5;
    }
    return ans;
}
int main() {
    int T, ca = 1;
    scanf("%d", &T);
    while(T--) {
        int Q;
        scanf("%d", &Q);
        printf("Case %d: ", ca++);
        int l = 1, r = INF, best = -1;
        //找到阶乘结尾大于等于Q个0的最小的数
        while(l <= r) {
            int mid = (l + r) / 2;
            if (get(mid) >= Q) best = mid, r = mid  - 1;
            else l = mid + 1;
        }
        //需要验证是不是刚好Q个0
        if (get(best) == Q) printf("%d\n", best);
        else printf("impossible\n");
    }
    return 0;
}

（srds，这道题初级班也出现过

E ：最小距离最大化

🔗 引用站外地址，请注意甄别
最小距离最大化
517coding

题意：在坐标轴上有 n 个点，从中选取 m 个点，使得这m个点两两之间的最小距离最大。

一眼二分

二分，然后 check 一下即可

值得注意的是，记得给原数组排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const int INF = (int) 1e9;

int a[N];

int n, m;
bool check(int x) {
    int cnt = 1;
    int lst = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i] - a[lst] >= x) {
            cnt++;
            lst = i;
            if (cnt == m) break;
        }
    }
    return cnt >= m;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1);
    int l = 0, r = INF, best = -1;
    while(l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) l = mid + 1, best = mid;
        else r = mid - 1;
    }
    printf("%d\n", best);
    return 0;
}

F：矩阵

🔗 引用站外地址，请注意甄别
矩阵
517coding

题意：

有一个 $N\times N$ 的矩阵。

第 $i$ 行第 $j$ 列的值为 $i^2+100000\times i+j^2-100000\times j+i\times j$

求矩阵中第 $M$ 小的数。

解法

写个函数方便测试：

1
2
3
long long f(int x,int y){
	return 1ll * x * x + 100000ll * x + 1ll * y * y - 100000ll * y + 1ll * x * y;
}

从 $f(1,1)$ 已知输出到 $f(5,5)$ ，结果如下：

1
2
3
4
5
3 -99993 -199987 -299979 -399969
100007 12 -99981 -199972 -299961
200013 100019 27 -99963 -199951
300021 200028 100037 48 -99939
400031 300039 200049 100061 75

观察到在列数不变的情况下，每一行的大小是递增的

这样我们就可以先二分答案，再枚举每一行，最后二分答案

（简单来说就是一个二分套二分

不开long long见祖宗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;

long long f(int x,int y){
	return 1ll * x * x + 100000ll * x + 1ll * y * y - 100000ll * y + 1ll * x * y;
}
int T, N;
long long M;
long long check(long long x) {
	long long ret = 0;
	for(int j = 1; j <= N; j++){
		int l = 1,r = N,  ans = 0;
		while(l <= r) {
			long long mid = (l + r) / 2;
			if(f(mid,j) <= x) {
				ans = mid;
				l = mid + 1;
			}
			else r = mid - 1;
		}
		ret += ans;
	}
	return ret;
}
int main() {
	scanf("%d",&T);
	while(T--){
		scanf("%d%lld", &N, &M);
		long long l = -1e12;
		long long r = 1e12;
		long long ans;
		while(l <= r){
			long long mid = (l + r) / 2;
			long long tmp = check(mid);
			if(tmp >= M) {
				ans = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}