作为一名忙碌的商人，约翰知道必须高效地安排他的时间。他有 N(1≤N≤1000) 个工作要做，比如给奶牛挤奶，清洗牛棚，修理栅栏之类的。

为了高效，约翰列出了所有工作的清单。第 i(1≤i≤N) 个工作需要 Ti​(1≤Ti​≤1000) 单位的时间来完成，而且必须在 1≤Si​≤106 或之前完成。现在是 0 时刻。约翰做一份工作必须直到做完才能停止。

所有的商人都喜欢睡懒觉。请帮约翰计算他最迟什么时候开始工作，可以让所有工作按时完成。（如果始终无法完成全部任务，输出 -1）

输入格式

第一行，一个整数 N

接下来 N 行，每行 2 个有空格分隔的整数 Ti​,Si​

输出格式

一行，一个整数，表示约翰可以开始工作的最晚时间，如果约翰无法完成所有工作，则为 -1

输入输出样例

输入 #1

4 
3 5 
8 14 
5 20 
1 16 

输出 #1

2 

说明/提示

【样例解释】

约翰有 4 个工作要做，分别需要 3、8、5 和 1 个时间单位，并且必须分别在时间 5、14、20 和 16 之前完成。

约翰必须在时间 2 开始第一个作业。然后他可以按此顺序完成第二、第四和第三项工作，以按时完成。

【代码示例】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;

struct task {
	int t;
	int s;
} T[MAXN];

bool cmp(task a, task b) {
	return a.s < b.s;
}

bool check(int x) {
	int sum = x;
	for (int i = 1; i <= n; i++) {
		sum += T[i].t;
		if (sum > T[i].s) {
			return false;
		}
	}
	return true;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> T[i].t >> T[i].s;
	}
	sort(T + 1, T + n + 1, cmp);
	int l = 0, r = 1e6, ans = -1;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (check(mid)) {
			l = mid + 1;
			ans = mid;
		} else {
			r = mid - 1;
		}
	}
	cout << ans;
}

当你正在散步时，突然出现了 N 只魔物。每只魔物拥有一个称为体力的数值，第 i 只魔物出现时的体力为 hi​。当某只魔物的体力降至 0 以下时，它会立刻消失。

幸运的是，你是一名熟练的魔法师，能够使用爆炸攻击魔物。每次爆炸时，你可以按以下方式减少魔物的体力：

• 选择一只仍然存活的魔物，以它为中心引发爆炸。爆炸中心的魔物体力减少 A，其余所有魔物的体力各自减少 B。其中 A 和 B 是已知的常数，且 A>B。

要彻底消灭所有魔物，最少需要引发多少次爆炸？

输入格式

输入以如下格式给出。

N A B h1​ h2​ … hN​

输出格式

输出消灭所有魔物所需的最小爆炸次数。

输入输出样例

输入 #1

4 5 3
8
7
4
2

输出 #1

2

输入 #2

2 10 4
20
20

输出 #2

4

输入 #3

5 2 1
900000000
900000000
1000000000
1000000000
1000000000

输出 #3

800000000

说明/提示

限制

• 输入中的所有数均为整数。
• 1≤N≤105
• 1≤B<A≤109
• 1≤hi​≤109

样例解释 1

可以通过以下方式，在 2 次爆炸内消灭全部魔物：

• 首先，以体力为 8 的魔物为中心引爆。四只魔物的体力分别变为 3，4，1，−1，最后一只魔物消失。
• 接着，再以剩余体力为 4 的魔物为中心引爆。剩下的三只魔物体力分别变为 0，−1，−2，于是全部消失。

样例解释 2

必须分别以每只魔物为中心进行 2 次爆炸，总共需要 4 次爆炸。

【代码示例】

#include <bits/stdc++.h>
using namespace std;
int n, a, b, h[100005];

bool cmp(int x, int y) {
	return x > y;
}

int ceil(int x, int y) {
	if (x % y == 0)
		return x / y;
	else
		return x / y + 1;
}//向上取整

bool check(long long x) {
	long long cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (h[i] <= x * b)
			continue;
		//若x次伤害为B的爆炸可以把他消灭把它消灭
		cnt += ceil(h[i] - x * b, a - b);
		//用伤害为A的爆炸将他消灭
	}
	return cnt <= x;
}

int main() {
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++)
		cin >> h[i];

	long long  l = 0, r = 1e18, ans = -1;
	while (l <= r) {
		long long mid = l + (r - l) / 2;
		if (check(mid)) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << ans;
}

题目描述

皮皮最近对于环保非常关注，他了解到深海里有很多很多垃圾，因此准备去深海开展一项垃圾清除活动。

经过探测，深海中一共有 n 个区域，环卫队会对所有区域都同时开展清理，清理速度为每秒 a 千克， 每一个区域的垃圾在清理 $t_i$秒后就会被清理干净。

为了达成清理 $M$ 千克垃圾的目标，请问环保人员最少需要在海里清理多久？

【输入格式】

输入共 2 行：
第 1 行：3 个空格隔开的正整数，分别为 n, M, a, 分别代表区域数量，清理垃圾的目标重量，每秒清理垃圾的重量。
第 2 行：n 个空格隔开的正整数，分别表示每个区域需要清理的时间。

【输出格式】

输出共 1 行
第 1 行：1 个整数，表示最少需要清理的时间

【输入输出样例#1】

输入#1

5 100 5
20 5 2 4 8

输出#1

5

【数据范围】

$1\le n\le 10^6,1\le t_i\le 10^7,1\le a\le 100.$输入保证一定能清理 M 千克的垃圾

【代码示例】

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

bool chk(int x) {
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		if (c[i] >= x) {
			sum += x * a;
		} else {
			sum += c[i] * a;
		}
	}
	return sum >= m;
}

int main() {
	cin >> n >> m >> a;
	for (int i = 1; i <= n; i++)
		cin >> c[i];
	int l = 1, r = 1e7, ans = -1;

	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (chk(mid)) {
			r = mid - 1;
			ans = mid;
		} else
			l = mid + 1;
	}
	cout << ans << endl;
}

题目描述

由于对计算机科学的热爱，以及有朝一日成为 「Bessie 博士」的诱惑，奶牛 Bessie 开始攻读计算机科学博士学位。经过一段时间的学术研究，她已经发表了 N 篇论文（1≤N≤105），并且她的第 i 篇论文得到了来自其他研究文献的 ci​ 次引用（0≤ci​≤105）。

Bessie 听说学术成就可以用 h 指数来衡量。h 指数等于使得研究员有至少 h 篇引用次数不少于 h 的论文的最大整数 h。例如，如果一名研究员有 4 篇论文，引用次数分别为 (1,100,2,3)，则 h 指数为 2，然而若引用次数为 (1,100,3,3) 则 h 指数将会是 3。

为了提升她的 h 指数，Bessie 计划写一篇综述，并引用一些她曾经写过的论文。由于页数限制，她至多可以在这篇综述中引用 L 篇论文（0≤L≤105），并且她只能引用每篇她的论文至多一次。

请帮助 Bessie 求出在写完这篇综述后她可以达到的最大 h 指数。

注意 Bessie 的导师可能会告知她纯粹为了提升 h 指数而写综述存在违反学术道德的嫌疑；我们不建议其他学者模仿 Bessie 的行为。

输入格式

输入的第一行包含 N 和 L。

第二行包含 N 个空格分隔的整数 c1​,…,cN​。

输出格式

输出写完综述后 Bessie 可以达到的最大 h 指数。

输入输出样例

输入 #1

4 0
1 100 2 3

输出 #1

2

输入 #2

4 1
1 100 2 3

输出 #2

3

说明/提示

样例解释 1

Bessie 不能引用任何她曾经写过的论文。上文中提到，(1,100,2,3) 的 h 指数为 2。

样例解释 2

如果 Bessie 引用她的第三篇论文，引用数会变为 (1,100,3,3)。上文中提到，这一引用数的 h 指数为 3。

测试点性质

• 测试点 1−7 满足 N≤100。
• 测试点 8−10 满足 N≤1000。
• 测试点 11−17 满足 N≤105。

【代码示例】

#include <bits/stdc++.h>
using namespace std;
int n, m, c[100005];

bool chk(int x) {
	int sum = 0;
	int mm = m;
	for (int i = 1; i <= n; i++) {
		if (c[i] >= x)
			sum++;
		if (c[i] == x - 1 && mm > 0) {
			sum++;
			mm--;
		}
	}
	return sum >= x;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> c[i];
	//if(m<=n) c[n+1]=m;
	//else c[n+1]=n;
	int l = 1, r = 1e5, ans = -1;

	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (chk(mid)) {
			l = mid + 1;
			ans = mid;
		} else
			r = mid - 1;
	}
	cout << ans << endl;
}

现给你一个长度为 $n$的序列 $a_1,\cdots ,a_n$​和 $m$个互不相同的整数 $b_1,\cdots ,b_m$​。你需要按照这 $m$个数对序列 $a$进行狠狠地切割。

具体的，对于一个数字 $i\in [1,n]$，如果存在一个整数 $j\in [1,m]$，使得 $a_i=b_j$，则将位置 $i$称为一个切割点。对序列 $a$中的每一个切割点，我们在这个位置进行一次狠狠地切割。方法是，将该位置的数字去除，然后在这个位置将其左右的序列/片段一分两半。

如果对狠狠地切割的定义有疑问，可以参照「样例 #1」及「样例解释 #1」进行理解。

你需要计算，在进行了所有可能的狠狠地切割后，序列被切割为了多少片段。

特别的，如果在切割后，某一段内没有数组，那这一段不可被叫做片段。同样的，如果 $1$或 $n$为切割点，其与开头和结尾之间也不存在片段。

如果对片段的概念有疑问，可以参照「样例 #2」及「样例解释 #2」进行理解。

【输入格式】

第一行为两个整数，依次表示序列 $a$的长度 $n$和序列 $b$的长度 $m$。
第二行有 $n$个整数，第 $i$个整数表示 $a_i$。
第三行有 $m$个整数，第 $i$个整数表示 $b_i$。

【输出格式】

输出一个整数，代表狠狠地切割后的片段的个数。

【输入输出样例#1】

输入#1

6 2
3 4 3 5 2 6
5 4

输出#1

3

【输入输出样例#2】

输入#2

6 3
3 4 3 5 2 6
3 5 6

输出#2

2

【说明提示】

样例 1 解释

在狠狠地切割前，序列 $a$a

如下所示：$\begin{array}{cccccc}3& 4& 3& 5& 2& 6\end{array}$

​$\begin{array}{cccccc}3& \mathrm{\mid }& 3& \mathrm{\mid }& 2& 6\end{array}$

​$\begin{array}{ccccc}\stackrel{\text{片段 1}}{\overbrace{3}}& \mathrm{\mid }& \stackrel{\text{片段 2}}{\overbrace{3}}& \mathrm{\mid }& \stackrel{\text{片段 3}}{\overbrace{26}}\end{array}$

样例 2 解释

以下我们展示去除之后的序列：

$\begin{array}{cccccc}\mathrm{\mid }& 4& \mathrm{\mid }& \mathrm{\mid }& 2& \mathrm{\mid }\end{array}$

​$\begin{array}{ccccccc}\stackrel{\text{这个不是片段}}{\overbrace{\phantom{\mathrm{}}}}\mathrm{\mid }& \stackrel{\text{片段 1}}{\overbrace{4}}& \mathrm{\mid }& \stackrel{\text{这个不是片段}}{\overbrace{\phantom{\mathrm{}}}}& \mathrm{\mid }& \stackrel{\text{片段 2}}{\overbrace{2}}& \mathrm{\mid }\stackrel{\text{这个不是片段}}{\overbrace{\phantom{\mathrm{}}}}\end{array}$​

数据规模与约定

• 对于 $30\mathrm{\%}$的数据，保证 $a$序列中没有任何元素在 $b$中出现过。形式化的，$\mathrm{\forall }i\in [1,n],\mathrm{\forall }j\in [1,m],a_i\mathrm{\ne }{b}_j$。
• 对于 $100\mathrm{\%}$的数据，保证 $1\le n,m\le 5\times 10^5$，$-10^{18}\le a_i,b_i\le 10^{18}$，序列 $b$中的元素两两不同。

提示

本题输入规模较大，建议考虑使用较快的读入读出方式。

【解题思路】

先将$b$序列排序，便于后续查找。然后遍历 $a$序列,通过二分查找法判断是否在$b$序列中。存在即分割，循环计数

【代码样例】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5 * 1e5 + 5;
long long a[MAXN];
long long b[MAXN];
int n, m;

bool isdivide(long long x) {
	auto i = lower_bound(b + 1, b + m + 1, x) - b;
	if (x == b[i]) {
		return true;
	} else {
		return false;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
	}
	sort(b + 1, b + m + 1); //排序
	int t = 0;
	int cnt = 0; //计数
	for (int i = 1; i <= n; i++) {
		if (isdivide(a[i])) {
			if (t > 0) {
				cnt++;
				t = 0;
			}
		} else {
			t++;
		}
	}
	if (t > 0) {
		cnt++;
	}
	cout << cnt << endl;

}

题目描述

给定长度为N的数列A = (A₁, A₂, …, A_N)， 和 整数K = 0, 1, 2, …, N−1，请问 A 中有多少个A_i （1 <= i <= n) 恰好包含 k 个大于它的不同正整数。

【输入格式】

共两行，
第一行，一个正整数 N，表示输入数的个数；
第二行，N个整数 A_i 。

【输出格式】

共N行，每行一个整数，分别表示K = 0, 1, 2, …, N−1时的答案。

【输入输出样例#1】

输入#1

6
2 7 1 8 2 8

输出#1

2
1
2
1
0
0

【输入输出样例#2】

输入#2

1
1

输出#2

1

【输入输出样例#3】

输入#3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

输出#3

2
1
2
1
2
1
1
0
0
0

【说明提示】

对于样例1的说明：
当 K 为 2 时.
A₁ = 2，A包含了 2 个不同的大于它的正整数：7、8；
A₂ = 7，A包含了 1 个不同的大于它的正整数：8；
A₃ = 1，A包含了 3 个不同的大于它的正整数：2、7、8；
A₄ = 8，A包含了 0 个不同的大于它的正整数：无；
A₅ = 2，A包含了 2 个不同的大于它的正整数：7、8；
A₆ = 8，A包含了 0 个不同的大于它的正整数：无；
​

【数据范围】

1 ≤ N ≤ 2 × 10⁵

1 ≤ A_i ≤ 10⁹

【代码样例】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2 * 1e5 + 5;
int n;
int a[MAXN];
int b[MAXN];
int k[MAXN];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + n + 1); //排序
	//去重
	int j = 1;
	b[j] = a[1];
	for (int i = 2; i <= n; i++) {
		if (a[i] != b[j]) {
			j++;
			b[j] = a[i];
		}
	}
	for (int i = 1; i <= n; i++) {
		int x = upper_bound(b + 1, b + j + 1, a[i]) - b;
		k[j - x + 1]++;
	}
	for (int i = 0; i < n; i++) {
		cout << k[i] << endl;
	}


}

题目描述

现有 m 所学校，每所学校预计分数线是 $a_i$​。有 n 位学生，估分分别为 $b_i$。

根据 n 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（分数线可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

【输入格式】

第一行读入两个整数 m,n。m 表示学校数，n 表示学生数。
第二行共有 m 个数，表示 m 个学校的预计录取分数。第三行有 n 个数，表示 n 个学生的估分成绩。

【输出格式】

输出一行，为最小的不满意度之和。

【输入输出样例#1】

输入#1

复制

4 3
513 598 567 689
500 600 550

输出#1

复制

32

【数据范围】

对于 80% 的数据，1 <= n,m <= 10000，估分和录取线 <= 1000000；
对于 100% 的数据，1 <= n,m <= 200000，估分和录取线 <= 1000000；

【代码样例】

#include <bits/stdc++.h>
using namespace std;
long long  m,n,cnt;
int a[200005],b[200005];
int main(){   
    cin>>m>>n;
    for(int i=1;i<=m;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(a+1,a+m+1);
    //sort(b+1,b+n+1);
     
    for(int i=1;i<=n;i++){
    	auto x=lower_bound(a+1,a+m+1,b[i])-a;
    	if(x==m+1) {
    		cnt+=abs(b[i]-a[m]);
    	} else if(x!=1) {
    		cnt+=min(abs(b[i]-a[x]),abs(b[i]-a[x-1]));
    	} else {
    		cnt=abs(b[i]-a[x]);	
    	}
    }
    cout<<cnt<<endl;
    return 0;
}

 题目描述

虽然 Miss Medusa 到了北京，领了科技创新奖，但是她还是觉得不满意。原因是：他发现很多人都和她一样获了科技创新奖，特别是其中的某些人，还获得了另一个奖项——特殊贡献奖。而越多的人获得了两个奖项，Miss Medusa就会越眼红。于是她决定统计有哪些人获得了两个奖项，来知道自己有多眼红。

【输入格式】

第一行两个整数 $n,m$，表示有 $n$ 个人获得科技创新奖，$m$ 个人获得特殊贡献奖。

第二行 $n$ 个正整数，表示获得科技创新奖的人的编号。

第三行 $m$ 个正整数，表示获得特殊贡献奖的人的编号。

【输出格式】

输出一行，为获得两个奖项的人的编号，按在科技创新奖获奖名单中的先后次序输出。

【输入输出样例#1】

输入#1

复制

4 3
2 15 6 8
8 9 2

输出#1

复制

2 8

【数据范围】

对于 $50\mathrm{\%}$ 的数据，$0\le n,m\le 1000$，获得奖项的人的编号 $<2\times 10^9$；

对于 $100\mathrm{\%}$ 的数据，$0\le n,m\le 10^6$，获得奖项的人的编号 $<2\times 10^{18}$。

输入数据保证第二行任意两个数不同，第三行任意两个数不同。

【代码样例】

#include <bits/stdc++.h>
using namespace std;
int n,m;
long long a1[1000005],a2[1000005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a1[i];
	for(int i=1;i<=m;i++) cin>>a2[i];
	sort(a2+1,a2+m+1);
	//sort(a1+1,a1+n+1);
	for(int i=1;i<=n;i++){
		if(a1[i]==a2[lower_bound(a2+1,a2+m+1,a1[i])-a2]){
			cout<<a1[i]<<" ";
		}
	}
}