Problem Address：http://poj.org/problem?id=3497
【前言】
昨天写了这道题的代码，交了返回CE。
一看发现POJ又崩溃了= =
后来又写多了一道。
今天回到学校，重新交了这两道题。
前者返回TLE，后者返回AC。
于是乎改啊改，不知道哪里TLE了，质疑二分写的不好。
很多次TLE后，修改了代码，改成map之类的，还是TLE。
最后找到某份代码，抄了个二分，然后就A掉了。
发现自己还是很不会写二分外面的那个东东，加一减一大于小于控制不好。
大概200+ms。
后来提交了第一次的代码，发现居然100+ms！
【思路】
题意：电脑的性能由其组件中性能最差的那一个决定，要求最大性能。
思路就是二分这个性能，然后对于每一个组件，找出其中大于这个性能的最小价格，累加起来。
如果不超过预算，则符合条件。
由于题意所给数据已排好序，所以可以省去排序一步。
对于每一个组件，可以先预处理好大于其quality的最小price，此后便无须重复判断。
200+的代码是把同类的组件放在同一个数组里。用map映射。
100+的代码是直接不修改，记录每一个组件在数组中的范围，然后查找的时候通过这些区间查找即可。
我觉得时间差距应该还是在map上。
此外，由于每个组件的个数并不是特别多，所以即使在查找组件中符合条件的个数时进行二分，效果也不是特别明显的。
【代码】
200+ms：
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
const int maxn = 1000;
map<string, int> map_index;
struct component
{
int price;
int quality;
int min_price;
}p[maxn+5][maxn+5];
int p_ct[maxn+5];
int seg[maxn+5][2];
bool cmp(const component &a, const component &b)
{
if (a.quality!=b.quality) return a.quality<b.quality;
else return a.price<b.price;
}
bool solve(int q, int b, int ct)
{
int i, j;
int sum = 0;
for (i=0; i<ct; i++)
{
for (j=0; j<p_ct[i]; j++)
{
if (p[i][j].quality>=q)
{
sum += p[i][j].min_price;
break;
}
}
// int low = 0, high = p_ct[i]-1, mid;//注释部分为在组件内部二分
// if (p[i][high].quality<q) return false;
// while(low<high)
// {
// mid = (low+high)/2;
// if (p[i][mid].quality>=q) high = mid;
// else low = mid+1;
// }
// sum += p[i][high].min_price;
if (j>=p_ct[i]) return false;
if (sum>b) return false;
}
return true;
}
int main()
{
int t;
int n, b;
int i, j;
int c, d;
char m_type[25], name[25];
string x;
int ct;
int index;
int high, low, mid;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &b);
memset(p_ct, 0, sizeof(p_ct));
map_index.clear();
ct = 0;
high = -INT_MAX;
low = INT_MAX;
for (i=0; i<n; i++)
{
scanf("%s %s", m_type, name);
x = "";
for (j=0; m_type[j]!='\0'; j++)
x += m_type[j];
if (map_index.find(x)==map_index.end())
{
map_index[x] = ct;
ct++;
}
index = map_index[x];
scanf("%d %d", &c, &d);
p[index][p_ct[index]].price = c;
p[index][p_ct[index]].quality = d;
if (d>high) high = d;
if (d<low) low = d;
p_ct[index]++;
}
for (i=0; i<ct; i++)
{
// sort(&p[i][0], &p[i][p_ct[i]], cmp);//已排好序，可以不排
p[i][p_ct[i]-1].min_price = p[i][p_ct[i]-1].price;
for (j=p_ct[i]-2; j>=0; j--)
{
if (p[i][j].price<p[i][j+1].min_price)
p[i][j].min_price = p[i][j].price;
else
p[i][j].min_price = p[i][j+1].min_price;
}
}
int flag = 0;
while(low<=high)
{
mid = (low+high)/2;
if (solve(mid, b, ct))
{
low = mid+1;
flag = 1;
}
else high = mid-1;
}
if (flag==0) printf("0\n");
else printf("%d\n", high);
}
return 0;
}
100+ms：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1000;
struct component
{
char m_type[25];
int price;
int quality;
int min_price;
}p[maxn+5];
int seg[maxn+5][2];
bool cmp(const component &a, const component &b)
{
int t = strcmp(a.m_type, b.m_type);
if (t<0) return true;
else if (t>0) return false;
else if (a.quality!=b.quality) return a.quality<b.quality;
else return a.price<b.price;
}
bool solve(int q, int b, int ct)
{
int i;
int low, high, mid;
int sum = 0;
for (i=0; i<ct; i++)
{
// for (j=seg[i][0]; j<=seg[i][1]; j++)//函数内注释部分为非组件内部二分代码
// {
// if (p[j].quality>=q)
// {
// sum += p[j].min_price;
// break;
// }
// }
low = seg[i][0];
high = seg[i][1];
while(low<high)
{
mid = (low+high)/2;
if (p[mid].quality>=q) high = mid;
else low = mid+1;
}
// if (j>seg[i][1]) return false;
if (p[high].quality<q) return false;
sum += p[high].min_price;
if (sum>b) return false;
}
return true;
}
int main()
{
int t;
int n, b;
int i, j;
char name[25];
int ct;
int high, low, mid;
scanf("%d", &t);
while(t--)
{
scanf("%d %d", &n, &b);
for (i=0; i<n; i++)
scanf("%s %s %d %d", p[i].m_type, name, &p[i].price, &p[i].quality);
// sort(p, p+n, cmp);//省去排序
memset(seg, 0, sizeof(seg));
ct = 0;
for (i=1; i<n; i++)
{
if (strcmp(p[i-1].m_type, p[i].m_type)!=0)
{
seg[ct][1] = i-1;
ct++;
seg[ct][0] = i;
}
}
seg[ct][1] = n-1;
ct++;
for (i=0; i<ct; i++)
{
p[seg[i][1]].min_price = p[seg[i][1]].price;
for (j=seg[i][1]-1; j>=seg[i][0]; j--)
{
if (p[j].price<p[j+1].min_price)
p[j].min_price = p[j].price;
else p[j].min_price = p[j+1].min_price;
}
}
high = -INT_MAX;
low = INT_MAX;
for (i=0; i<n; i++)
{
if (p[i].quality>high) high = p[i].quality;
if (p[i].quality<low) low = p[i].quality;
}
int flag = 0;
while(low<=high)
{
mid = (low+high)/2;
if (solve(mid, b, ct))
{
flag = 1;
low = mid + 1;
}
else high = mid-1;
}
if (flag==0) printf("0\n");
else printf("%d\n", high);
}
return 0;
}
【P.S】
为神马二分的函数总写不好%>_<%