伐木机不要石头!!!(easy version)
本题有对应的hard version,区别仅在多次询问中。保证easy version的测试用例集是hard version的真子集,通过困难版本的代码经过简单修改可直接通过简单版
看着家里贫瘠的资源,是时候出发采点木头了!可你突然发现家里没石头,连伐木机都造不好……于是,可露希尔替你发明了无敌手斧,只要木头!可是他的耐久度只有 1,使用完该手斧砍伐掉一棵树之后,该手斧将损坏无法继续使用,也就是一个无敌手斧只能砍一棵树。现在你已经拥有了大量的无敌手斧,信心百倍的进入了林区。你面前是 n棵排成一列的树,每棵树的坚硬程度为 ai,第一棵树的位置位于 1号点,第二棵位于 2号依次类推,直到第 n棵树。而你背包里的无敌手斧有 m个,每个的破坏程度为 bj,当一个无敌手斧的破坏程度不小于一棵树的坚硬程度时,无敌手斧可以将这棵树砍倒,砍倒后你就可以拿走这棵树的木材。那聪明的博士就会想了:如果博士想使用无敌手斧砍伐位置在 1到 n 这段区域内的树木,最多可以带走多少棵树的木材呢?
输入描述:第一行输入二个数 n,m 别表示树的棵数,无敌手斧的个数。 第二行输入 n个数 ai, 表示第 i棵树的坚硬程度。 第三行输入 m个数 bj, 表示第 j 个无敌手斧的破坏程度。 数据保证 1≤n,m≤10^5,1≤ai≤10^9,1≤bj≤10^9。
输出描述:输出一行非负整数,代表可拿走多少棵树的木材。
输入
5 5 1 2 3 4 5 1 1 4 4 5 输出:4 说明:第 1 棵树可以匹配上第 1个手斧。第 2棵树可以匹配上第 3个手斧。第 4棵树可以匹配上第 4个手斧。第 5棵树可以匹配上第 5个手斧。所以答案为 4。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int sum, n, m, a[N], b[N];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int j = 1; j <= m; j++) cin >> b[j];
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
for (int i = 1, j = 1; i <= n && j <= m; i++) {
while (j <= m && i <= n && a[i] > b[j]) j++;
if (j <= m && i <= n) {
sum++;
j++;
}
}
cout << sum;
return 0;
}
ios::sync_with_stdio(0)
、cin.tie(0)
和cout.tie(0)
是为了关闭标准IO与Cstdio之间的同步,提高输入输出效率。