[cpp]
/*************************************************************************
> File Name: 12124.cpp
> Author: BobLee
> Mail: [email protected]
> Created Time: Mon 25 Mar 2013 08:36:44 PM CST
************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
using namespace std;
const int maxn = 1010;
struct co
{
int price;
int qua;
};
map<string,int> id;
vector<co> 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<cnt;i++)
{
int cheap = B+1;
int m = com[i].size();
for(int j=0;j<m;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<N;i++)
com[i].clear();
for(int i=0;i<N;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<R)
{
int M=(L+R+1)/2;
//cout<<L<<" "<<R<<" "<<M<<endl;
if(fun(M))
{
L=M;
}
else
R=M-1;
//cout<<L<<" "<<R<<" "<<M<<endl;
//getchar();
// if(M==0)
// break;
}
printf("%d\n",L);
}
return 0;
}
/*************************************************************************
> File Name: 12124.cpp
> Author: BobLee
> Mail: [email protected]
> Created Time: Mon 25 Mar 2013 08:36:44 PM CST
************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
using namespace std;
const int maxn = 1010;
struct co
{
int price;
int qua;
};
map<string,int> id;
vector<co> 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<cnt;i++)
{
int cheap = B+1;
int m = com[i].size();
for(int j=0;j<m;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<N;i++)
com[i].clear();
for(int i=0;i<N;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<R)
{
int M=(L+R+1)/2;
//cout<<L<<" "<<R<<" "<<M<<endl;
if(fun(M))
{
L=M;
}
else
R=M-1;
//cout<<L<<" "<<R<<" "<<M<<endl;
//getchar();
// if(M==0)
// break;
}
printf("%d\n",L);
}
return 0;
}
可以看到我取中值的時候，用的是向上取整。（實際上是劉汝佳這麼寫的）
我當時寫的是 M=(L+R)/2; 也就是向下取整的意思，但是在不同提交的遇到了一個問題。
我的TLE了。
當時我是百思不得其解，後來仔細思考了之後發現了一個問題。那就是你在這個程序中是求一個合理區間的最大值。
舉個例子，假如我們的最後要取的值為5，區間也是[0,5]，用向下取整的話
則
L R M
0 5 2
2 5 3
3 5 4
4 5 4
4 5 4
。。。
發現問題了吧，這個時候就會陷入死循環。
再來一個例子，假如我們是求一個合理區間的最小值，二分的代碼
[cpp]
while(L<R)
{
M=(L+R+1)/2;
if(ok(M))
R=M;
else
L=M+1;
}
while(L<R)
{
M=(L+R+1)/2;
if(ok(M))
R=M;
else
L=M+1;
}我們還是用向上取整來做。區間為[0,5]，最後的值為0
L R M
0 5 3
0 3 2
0 2 1
0 1 1
0 1 1
。。。
又陷入了死循環，但是我們可以發現如果這時用向下取整就是可行的了。
所以由上面就可以得出，
當我們使用二分法求某個合理區間最值的時候，我們要十分注意兩個端點的極端值的情況。
當然還有一種更保險的方法
那就是不用上面的二分的方法
在二分的時候用另外一個變量來記錄合理值，然後L=M+1 OR R=M-1
所以這樣的話是不回陷入到死循環裡面去的
這就是我由這T想到了，好久不寫博客了。還是要撿起來啊。
