关于二分法中取中间值时向下和向上取整的问题（由大白LA3971想到的） (一)

[cpp]
/*************************************************************************
> File Name: 12124.cpp
> Author: BobLee
> Mail: wustboli@gmail.com
> Created Time: Mon 25 Mar 2013 08:36:44 PM CST
************************************************************************/

#include
#include
#include
#include
#include
#include
#include

/*************************************************************************
> File Name: 12124.cpp
> Author: BobLee
> Mail: wustboli@gmail.com
> Created Time: Mon 25 Mar 2013 08:36:44 PM CST
************************************************************************/

#include
#include
#include
#include
#include
#include
#include

const int maxn = 1010;

struct co
{
int price;
int qua;
};

map id;
vector com[maxn];
int N,B;
int cnt;

int ID(string s)
{
if(!id.count(s))
id[s] = cnt++;
return id[s];
}

bool fun(int q)
{
int sum = 0;
for(int i=0;i {
int cheap = B+1;
int m = com[i].size();
for(int j=0;j {
if(com[i][j].qua>=q)
cheap = min(cheap,com[i][j].price);
}
if(cheap > B)
return false;
sum+=cheap;
if(sum>B)
return false;
}
return true;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&N,&B);
char type[30],name[30];
int price,quaa;
int maxq = 0;
cnt=0;
for(int i=0;i com[i].clear();
for(int i=0;i {
scanf("%s%s%d%d",type,name,&price,&quaa);
maxq = max(maxq,quaa);
com[ID(type)].push_back((co){price,quaa});
}
int L=0;
int R=maxq;
while(L {
int M=(L+R+1)/2;
//cout< if(fun(M))
{
L=M;
}
else
R=M-1;
//cout< //getchar();
// if(M==0)
// break;
}
printf("%d\n",L);
}
return 0;

}

可以看到我取中值的时候，用的是向上取整。（实际上是刘汝佳这么写的）

我当时写的是 M=(L+R)/2; 也就是向下取整