题意:
给出N个小时,分配这些小时去写若干份论文,若用1小时写一份论文,该论文会被引用A次,新写一篇论文的话,全面的论文会被新论文引用一次.
找最大的H,H是指存在H遍论文,而且这些论文各被引用大于H次.
思路:
第一步,我们要想怎么样分配这些时间,毫无疑问,当N个小时写N份论文时为最优方案. 证明如下: 如果一开始的A>数量的话,就一直写新的:(没疑问吧!!!,如果A>数量,你还写旧的不是浪费时间吗???) 然后我们就会到一个分水岭 到达 A=数量(这时还是可以接受的,因为这里的A也算进去了,再开一个就变成不满足了,因为假设它当前的数量为x) ,明显A<x+1. 现在我就想让当前这个不满足的满足,我们可以有两个选择(继续给他加A,或者新开一个给他+1). 划重点啦!!::因为数量也是+1的所以我们取最优的方案(+1)就行了.
所以题目就变成了 N个小时 写了N遍论文 : 维护一个公差为1的等差数量 其中 首项为 N-1+a ,最后一项为a+N-N. 我们设答案为B篇. 所以数量(B)=被引用(N-B+a)
解得B=(a+N)/2;
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,a;
while(scanf("%d%d",&n,&a)!=EOF)
cout<<(a+n)/<<endl;
return ;
}
new Code