洛谷 P2440木材加工 P2678跳石头 P1314聪明的质检员 P1084借教室 P1902刺杀大师 P1163银行贷款

都是二分+很裸的算法，就不写繁冗的题解了注意：求xmax则 l 右移反之左移。

骑驴看星星a

633人浏览 · 2025-03-01 11:30:01

骑驴看星星a · 2025-03-01 11:30:01 发布

都是二分+很裸的算法，就不写繁冗的题解了
注意：求xmax则 l 右移
反之左移

P2440 木材加工

题目描述

木材厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度均为 $l$ 的小段木头（木头有可能有剩余）。

当然，我们希望得到的小段木头越长越好，请求出 $l$ 的最大值。

木头长度的单位是 $cm\text{cm}$ ，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 $11$ 和 $21$ ，要求切割成等长的 $6$ 段，很明显能切割出来的小段木头长度最长为 $5$ 。

输入格式

第一行是两个正整数 $n, k$ ，分别表示原木的数量，需要得到的小段的数量。

接下来 $n$ 行，每行一个正整数 $L_i$ ，表示一根原木的长度。

输出格式

仅一行，即 $l$ 的最大值。

如果连 $1cm\text{1cm}$ 长的小段都切不出来，输出 0。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

数据规模与约定

对于 $100%100\%$ 的数据，有 $1≤n≤1051\le n\le 10^5$ ， $1≤k≤1081\le k\le 10^8$ ， $1≤Li≤108(i∈[1,n])1\le L_i\le 10^8(i\in[1,n])$ 。

#include <bits/stdc++.h>
using namespace std;
long long n, k, a[1000005];

bool check(long long x) {
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += a[i] / x;
	}
	return ans >= k;
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	long long l = 0, r = 100000001;
	long long mid;
	
	while (l + 1 < r) {
		mid = (l + r) / 2;
		if (check(mid)) l = mid;
		else r = mid;
	}
	cout << l << endl;
	return 0;
}

P2678 跳石头

P2678 [NOIP 2015 提高组] 跳石头

题目描述

一年一度的“跳石头”比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 $L, N, M$ ，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $\geq 1$ 且 $\geq M \geq 0$ 。

接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i\,( 0 < D_i < L)$ ，表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

输入输出样例 1 说明

将与起点距离为 $2$ 和 $14$ 的两个岩石移走后，最短的跳跃距离为 $4$ （从与起点距离 $17$ 的岩石跳到距离 $21$ 的岩石，或者从距离 $21$ 的岩石跳到终点）。

数据规模与约定

对于 $20%20\%$ 的数据， $\le M \le N \le 10$ 。
对于 $50%50\%$ 的数据， $\le M \le N \le 100$ 。
对于 $100%100\%$ 的数据， $\le M \le N \le 50000,1 \le L \le 10^9$ 。

#include<bits/stdc++.h>
using namespace std;
int L, n, M, a[500005];
bool check(int x)
{
	int last = 0, cnt = 0;
	for(int i = 1; i <=n + 1; i++){
		if(a[i] - a[last] < x)  cnt++;
		else last = i;
	} 
	return cnt <= M;
}
int find(){
	int l = 0, r = 1e9+1;
	while(l + 1 < r){
		int mid = (l + r)/2;
		if(check(mid)) l = mid;
		else r = mid;
	}return l; 
}
int main(){
	cin >> L >> n >> M;
	for(int i = 1; i <= n; i++)cin >> a[i];
	a[n+1] = L;
	cout << find();
	return 0;
}

P1314 聪明的质监员

题目描述

小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 $n$ 个矿石，从 $1$ 到 $n$ 逐一编号，每个矿石都有自己的重量 $w_i$ 以及价值 $v_i$ 。检验矿产的流程是：

给定$ m$ 个区间 $l_i,r_i]$ ；
选出一个参数 $W$ ；
对于一个区间 $l_i,r_i]$ ，计算矿石在这个区间上的检验值 $y_i$ ：

$yi=∑j=liri[wj≥W]×∑j=liri[wj≥W]vjy_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j$

其中 $j$ 为矿石编号。

这批矿产的检验结果 $y$ 为各个区间的检验值之和。即： $∑i=1myi\sum\limits_{i=1}^m y_i$

若这批矿产的检验结果与所给标准值 $s$ 相差太多，就需要再去检验另一批矿产。小T 不想费时间去检验另一批矿产，所以他想通过调整参数 $W$ 的值，让检验结果尽可能的靠近标准值 $s$ ，即使得 $∣ s - y ∣$ 最小。请你帮忙求出这个最小值。

输入格式

第一行包含三个整数 $n, m, s$ ，分别表示矿石的个数、区间的个数和标准值。

接下来的 $n$ 行，每行两个整数，中间用空格隔开，第 $i + 1$ 行表示 $i$ 号矿石的重量 $w_i$ 和价值 $v_i$ 。

接下来的 $m$ 行，表示区间，每行两个整数，中间用空格隔开，第 $i + n + 1$ 行表示区间 $l_i,r_i]$ 的两个端点 $l_i$ 和 $r_i$ 。注意：不同区间可能重合或相互重叠。

输出格式

一个整数，表示所求的最小值。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

【输入输出样例说明】

当 $W$ 选 $4$ 的时候，三个区间上检验值分别为 $20, 5, 0$ ，这批矿产的检验结果为 $25$ ，此时与标准值 $S$ 相差最小为 $10$ 。

【数据范围】

对于 $10% $ 的数据，有 $1 \leq n, m \leq 10$ ；

对于 $30% $的数据，有 $1 \leq n, m \leq 500$ ；

对于 $50% $ 的数据，有 $ 1 ≤n ,m≤5,000$；

对于 $70%70\%$ 的数据，有 $1 \leq n, m \leq 10, 000$ ；

对于 $100%100\%$ 的数据，有 $ 1 ≤n ,m≤200,000$， $0 < w_i,v_i≤10^6$ ， $0 < s≤10^{12}$ ， $1 ≤l_i ≤r_i ≤n$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200010;

int n, m, w[N], v[N], l[N], r[N];
ll s, sn[N], sv[N], ans = 1e18;

bool check(ll W) {
    memset(sn, 0, sizeof(sn));
    memset(sv, 0, sizeof(sv));
    for (int i = 1; i <= n; i++) {
        if (w[i] >= W) {
            sn[i] = sn[i - 1] + 1;
            sv[i] = sv[i - 1] + v[i];
        } else {
            sn[i] = sn[i - 1];
            sv[i] = sv[i - 1];
        }
    }
    ll y = 0;
    for (int i = 1; i <= m; i++) {
        y += (sn[r[i]] - sn[l[i] - 1]) * (sv[r[i]] - sv[l[i] - 1]);
    }
    ans = min(ans, abs(y - s));
    return y <= s;
}

ll find() {
    ll l = 0, r = 1e6 + 1;
    while (l + 1 < r) {
        ll mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return ans;
}

int main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> l[i] >> r[i];
    }
    cout << find() << endl;
    return 0;
}

P1083 [NOIP 2012 提高组] 借教室

题目描述

在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 $n$ 天的借教室信息，其中第 $i$ 天学校有 $r_i$ 个教室可供租借。共有 $m$ 份订单，每份订单用三个正整数描述，分别为 $d_j,s_j,t_j$ ，表示某租借者需要从第 $s_j$ 天到第 $t_j$ 天租借教室（包括第 $s_j$ 天和第 $t_j$ 天），每天需要租借 $d_j$ 个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 $d_j$ 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 $s_j$ 天到第 $t_j$ 天中有至少一天剩余的教室数量不足 $d_j$ 个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 $n, m$ ，表示天数和订单的数量。

第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $r_i$ ，表示第 $i$ 天可用于租借的教室数量。

接下来有 $m$ 行，每行包含三个正整数 $d_j,s_j,t_j$ ，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 $1$ 开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数 $0$ 。否则（订单无法完全满足）

输出两行，第一行输出一个负整数 $- 1$ ，第二行输出需要修改订单的申请人编号。

输入输出样例 #1

输入 #1

输出 #1

-1 
2

说明/提示

【输入输出样例说明】

第 $1 $份订单满足后，$4 $天剩余的教室数分别为 $0, 3, 2, 3$ 。第 $2$ 份订单要求第 $2 $天到第 $4$ 天每天提供 $3$ 个教室，而第 $3$ 天剩余的教室数为$ 2$，因此无法满足。分配停止，通知第 $2$ 个申请人修改订单。

【数据范围】

对于 $10%10\%$ 的数据，有 $1≤n,m≤101\le n,m\le 10$ ；

对于 $30%30\%$ 的数据，有 $1≤n,m≤10001\le n,m\le 1000$ ；

对于 $70%70\%$ 的数据，有 $\le n,m \le 10^5$ ；

对于 $100%100\%$ 的数据，有 $\le n,m \le 10^6$ ， $\le r_i,d_j\le 10^9$ ， $\le s_j\le t_j\le n$ 。

NOIP 2012 提高组第二天第二题

2022.2.20 新增一组 hack 数据

暴力做法，会tle一些点

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;

int n, m, r[N], d[N], s[N], t[N];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> d[i] >> s[i] >> t[i];
    }
    for (int i = 1; i <= m; i++) {
        bool flag = true;
        for (int j = s[i]; j <= t[i]; j++) {
            if (r[j] < d[i]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            for (int j = s[i]; j <= t[i]; j++) {
                r[j] -= d[i];
            }
        } else {
            cout << -1 << endl;
            cout << i << endl;
            return 0;
        }
    }
    cout << 0 << endl;
    return 0;
}

差分和二分

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, m;
int r[N],d[N],s[N],t[N];
long long num[N];

bool check(int x){
	memset(num, 0 ,sizeof num);
	for(int i = 1;i <=x ; i++){//枚举订单 
		num[s[i]]+=d[i];
		num[t[i]+1]-=d[i]; //差分 
	}
	for(int i = 1; i <= n; i++){
		num[i] += num[i-1];
		if(num[i]>r[i])return false;
	}
	return true; 
} 
int find(){
	int l = 0,r = m+1;
	while( l+1 < r){
		int mid = l+r>>1;
		if(check(mid))l = mid;
		else r =mid;
	}
	return l;
} 
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> r[i];
	} 
	for(int i = 1; i <= m; i++){
		cin >> d[i] >> s[i] >> t[i];
	}
	cout << find(); 
	return 0;
}

P1902 刺杀大使

题目描述

某组织正在策划一起对某大使的刺杀行动。他们来到了使馆，准备完成此次刺杀，要进入使馆首先必须通过使馆前的防御迷阵。

迷阵由 $n×mn\times m$ 个相同的小房间组成，每个房间与相邻四个房间之间有门可通行。在第 $n$ 行的 $m$ 个房间里有 $m$ 个机关，这些机关必须全部打开才可以进入大使馆。而第 $1$ 行的 $m$ 个房间有 $m$ 扇向外打开的门，是迷阵的入口。除了第 $1$ 行和第 $n$ 行的房间外，每个房间都被使馆的安保人员安装了激光杀伤装置，将会对进入房间的人造成一定的伤害。第 $i$ 行第 $j$ 列造成的伤害值为 $p_{i,j}$ （第 $1$ 行和第 $n$ 行的 $p$ 值全部为 $0$ ）。

现在某组织打算以最小伤害代价进入迷阵，打开全部机关，显然，他们可以选择任意多的人从任意的门进入，但必须到达第 $n$ 行的每个房间。一个士兵受到的伤害值为他到达某个机关的路径上所有房间的伤害值中的最大值，整个部队受到的伤害值为所有士兵的伤害值中的最大值。现在，这个恐怖组织掌握了迷阵的情况，他们需要提前知道怎么安排士兵的行进路线可以使得整个部队的伤害值最小。

输入格式

第一行有两个整数 $n, m$ ，表示迷阵的大小。

接下来 $n$ 行，每行 $m$ 个数，第 $i$ 行第 $j$ 列的数表示 $p_{i,j}$ 。

输出格式

输出一个数，表示最小伤害代价。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

$50%50\%$ 的数据， $\leq 100$ ；
$100%100\%$ 的数据， $\leq 1000$ ， $pi,j≤1000p_{i,j} \leq 1000$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;

int n, m, p[N][N];
bool vis[N][N];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

bool dfs(int x, int y, int P) {
    if (x == n) return true;
    vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i];
        int b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && !vis[a][b] && p[a][b] <= P) {
            if (dfs(a, b, P)) return true;
        }
    }
    return false;
}

int find() {
    int l = -1, r = 1001;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        memset(vis, 0, sizeof(vis));
        if (dfs(1, 1, mid)) r = mid;
        else l = mid;
    }
    return r;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> p[i][j];
        }
    }
    cout << find();
    return 0;
}

P1163 银行贷款

题目描述

当一个人从银行贷款后，在一段时间内他（她）将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计。

输入格式

三个用空格隔开的正整数。

第一个整数表示贷款的原值 $w_0$ ，第二个整数表示每月支付的分期付款金额 $w$ ，第三个整数表示分期付款还清贷款所需的总月数 $m$ 。

输出格式

一个实数，表示该贷款的月利率（用百分数表示），四舍五入精确到 $0.1%0.1\%$ 。

数据保证答案不超过 $300.0%300.0\%$ 。

输入输出样例 #1

输入 #1

1000 100 12

输出 #1

2.9

说明/提示

数据保证， $\leq w_0, w\leq 2^{31}-1$ ， $\leq m\leq 3000$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
typedef long double ld;
ld a, b, c;
bool check(ld r) {
    ld s = a;
    for (int i = 0; i < c; i++) {
        s = s * (1 + r) - b;
    }
    return s >= 0;
}

ld find() {
    ld l = 0, r = 10; 
    while(r - l > 1e-5) { 
        ld mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;  
        } else {
            l = mid; 
        }
    }
    return r; //找的是最小
}

int main() {
    cin >> a >> b >> c;
    ld r = find();
    cout << fixed << setprecision(1) << r * 100 << endl;  
    return 0;
}