本文主要是介绍CodeForces 387B George and Round，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：http://codeforces.com/problemset/problem/387/B
George and Round
George decided to prepare a Codesecrof round, so he has prepared m problems for the round. Let's number the problems with integers 1 through m. George estimates the i-th problem's complexity by integer bi.
To make the round good, he needs to put at least n problems there. Besides, he needs to have at least one problem with complexity exactly a1, at least one with complexity exactly a2, ..., and at least one with complexity exactly an. Of course, the round can also have problems with other complexities.
George has a poor imagination. It's easier for him to make some already prepared problem simpler than to come up with a new one and prepare it. George is magnificent at simplifying problems. He can simplify any already prepared problem with complexity c to any positive integer complexity d (c ≥ d), by changing limits on the input data.
However, nothing is so simple. George understood that even if he simplifies some problems, he can run out of problems for a good round. That's why he decided to find out the minimum number of problems he needs to come up with in addition to the m he's prepared in order to make a good round. Note that George can come up with a new problem of any complexity.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 3000) — the minimal number of problems in a good round and the number of problems George's prepared. The second line contains space-separated integers a1, a2, ..., an (1 ≤ a1 < a2 < ... < an ≤ 106) — the requirements for the complexity of the problems in a good round. The third line contains space-separated integers b1, b2, ..., bm (1 ≤ b1 ≤ b2... ≤ bm ≤ 106) — the complexities of the problems prepared by George.
Output
Print a single integer — the answer to the problem.
Sample test(s)
3 5 1 2 3 1 2 2 3 3
0
3 5 1 2 3 1 1 1 1 1
2
3 1 2 3 4 1
3
Note
In the first sample the set of the prepared problems meets the requirements for a good round.
In the second sample, it is enough to come up with and prepare two problems with complexities 2 and 3 to get a good round.
In the third sample it is very easy to get a good round if come up with and prepare extra problems with complexities: 2, 3, 4.
大意——已知有m个准备好的问题以及它们的复杂度，这些问题的复杂度可以经过处理而降低，现在又给出被要求的n个具体的问题以及它们的复杂度，问：最少还要几个问题，才能达到被要求的题数及相应的复杂度？
思路——一道简单的贪心题。既然要找到最小题数，那么我们就需要在已有的问题中找到满足条件的最大题数。因为两类问题的复杂度已经按从小到大的顺序排列好了，所以也就是说将m道题的复杂度分别与n道题的复杂度比较即可，如果m道题之一的复杂度大于等于n道题之一的复杂度，则计数加一，最后用总题数减去满足条件的题数即为答案。注意：不可以重复比较，即如果m道题之一已经与n道题之一比较但不满足条件，则在m中继续往下选择一个与当前n中的比较；如果满足条件，则在m中、n中都要继续往下选择一个再比较。
复杂度分析——时间复杂度:O(n+m),空间复杂度:O(n+m)
附上AC代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
//#pragma comment(linker, "/STACK:102400000, 102400000")
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const double e = exp(1.0);
const double eps = 1e-8;
const int maxn = 3005;
int reque[maxn], prep[maxn];
int n, m;int main()
{ios::sync_with_stdio(false);while (~scanf("%d%d", &n, &m)){for (int i=0; i<n; i++)scanf("%d", reque+i);for (int i=0; i<m; i++)scanf("%d", prep+i);int cnt=0, index=0;while (cnt<n && index<m){if (prep[index] >= reque[cnt])cnt++;index++;}printf("%d\n", n-cnt);}return 0;
}
这篇关于CodeForces 387B George and Round的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
