频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
贪心-Code forces -387B -George and Round
2014-05-08 11:24:01         来源:贪心-Code forces -387B -George and Round  
收藏   我要投稿

Code forces -387B -George and Round

description

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?

Output

Print a single integer — the answer to the problem.

Sample Input

3 5

1 2 3

1 2 2 3 3

3 5

1 2 3

1 1 1 1 1

3 1

2 3 4

1

Sample Output

0

2

3

微笑大意:乔治要为比赛命题,共n道,每道题的复杂度给出。他自己已经准备好了m道题,复杂度也给出。若命题的复杂度不低于要求的复杂度,则认为此题合格。

问:乔治尽可能多的用自己的题,那么他最少还得出几道新题?

分析:尽量多用已有的题,就要求对自己的题按复杂度由低到高排序,从头到尾遍历,若能用则用(贪心)。对要求的题也排序是为了便于比较。

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:基类指针和派生类指针的使用总结2
下一篇:hdu 3006 The Number of set(思维+壮压DP)
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站