AOJ 846.勤劳的出题人

149


题目


点击显/隐题目

小蓝最近要办一场程序设计比赛, 要出一些题目.
从无到有原创一道题是很难的一件事情, 好在小蓝平时积累了m道现成的题目, 记这m道题的编号为1到m, 这m道题的复杂度记为bi(1<=i<=m).
另外为了保证比赛的质量, 小蓝指定了一个复杂度标准, 即, 小蓝至少需要出n道题, 复杂度分别恰好是ai(1<=i<=n).
小蓝可以通过降低题目难度将现成的一道难度为c的题目改编成难度为d(d<=c)的题目, 一道现成题最多使用一次; 也可以原创一道任意难度的题目, 鉴于原创的难度, 小蓝希望原创的题目越少越好.
现在请你帮忙判断, 小蓝至少需要原创多少道题.





第一行: 两个数, n和m,(1 <= n, m <= 3000)
第二行: n个数, 即a1, a2, ..., an;
第三行: m个数, 即b1, b2, ..., bm
(1 <= ai, bi <= 1000,000)





一个整数, 即小蓝至少需要原创的题目数





3 5
1 2 3
1 1 1 1 4





1





题解



分别对 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 upperbound(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.syncwithstdio(false);

int n,m;
while(cin >> n >> m){
memset(flag,false,sizeof(flag));
for(int i=0;icin >> a[i];
for(int i=0;icin >> b[i];
sort(a,a+n);
sort(b,b+m);
int ans=0;
int bpos=0;
for(int i=0;iwhile(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) / CLOCKSPERSEC);
#endif
return 0;
}

发布评论
  • 点击查看/关闭被识别为广告的评论