这是一篇最后编辑于 8 年前 的文章，其内容可能与目前实际情况差异较大，请注意甄别
题目
{% raw %}
{% endraw %} 小蓝最近要办一场程序设计比赛, 要出一些题目. 从无到有原创一道题是很难的一件事情, 好在小蓝平时积累了m道现成的题目, 记这m道题的编号为1到m, 这m道题的复杂度记为bi(1<=i<=m). 另外为了保证比赛的质量, 小蓝指定了一个复杂度标准, 即, 小蓝至少需要出n道题, 复杂度分别恰好是ai(1<=i<=n). 小蓝可以通过降低题目难度将现成的一道难度为c的题目改编成难度为d(d<=c)的题目, 一道现成题最多使用一次; 也可以原创一道任意难度的题目, 鉴于原创的难度, 小蓝希望原创的题目越少越好. 现在请你帮忙判断, 小蓝至少需要原创多少道题.
{% raw %}
{% endraw %}
第一行: 两个数, n和m,(1 <= n, m <= 3000)
第二行: n个数, 即a1, a2, ..., an;
第三行: m个数, 即b1, b2, ..., bm
(1 <= ai, bi <= 1000,000)
{% raw %}
{% endraw %}
一个整数, 即小蓝至少需要原创的题目数
{% raw %}
{% endraw %}
3 5
1 2 3
1 1 1 1 4
{% raw %}
题解
分别对 a 和 b 排序
对于每个要求的 a ,都选择尽可能小的 b
注意 a 比 b 还多的情况
最后求还剩下的题目数
贪心跑一边即可
代码
```cpp 勤劳的出题人 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 /*/ #define debug #include
//*/ #include #include #include #include using namespace std;const int maxn = 3005;
int a[maxn];
int b[maxn];
bool flag[maxn];
typedef int LL;
int upper_bound(LL *arr,int size, LL key) {
int mid;
int first = 0;
int half;
while (size > 0) {
half = size >> 1;
mid = half + first;
if (arr[mid] > key) {
size = half;
} else {
first = mid + 1;
size = size - half - 1;
}
}
return first;
}
int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);
int n,m;
while(cin >> n >> m){
memset(flag,false,sizeof(flag));
for(int i=0;i<n;i++)
cin >> a[i];
for(int i=0;i<m;i++)
cin >> b[i];
sort(a,a+n);
sort(b,b+m);
int ans=0;
int bpos=0;
for(int i=0;i<n;i++){
while(1){
if(bpos>=m){
ans = n-i;
break;
}
if(b[bpos]>=a[i]){
bpos++;
break;
}
bpos++;
}
if(ans)
break;
}
cout << ans << endl;
}
#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}
</div>