题目

{% 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 %}

{% endraw %}

{% raw %}

{% endraw %}

题解

分别对 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>

AOJ 846.勤劳的出题人

题目

题解

代码