HOJ 2608 Assemble(二分)

各部品は、quality、price、name、typeを含む構造体で保存する.
まずquality降順で並べ替え、並べ替え時に同類の部品を散らさないように注意し、同じ種類の部品がつながっていることを保証します.
さらにcomponets配列を用いて,iからjまでのどの部品かを記録する.componets[i]=0、componets[i+1]=3のように、0~2番目のレコードは部品iに属することが分かる.
そして品質について二分する.質量の範囲はすべての部品の質量の最大、最小値をとります.
すべての部品タイプにおいて、この品質以上でbudgetを超えないものを満たすことができれば、return true、midを高くして判断します.最後にできるだけ高い最低品質を得た.
そうでなければreturn false.midを下げる.
とにかく、典型的な二分です.
 
しかし、いつもいろいろな細部でうまく処理できず、不注意な欠点をよく犯し、debugは長い間間違いを見つけられなかった.時間がもったいない気がします.
MACコードは以下の通りである.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

struct element
{
    int price,quality;
    char str1[21],str2[21];
};
element elem[1001];
int componets[1001];
int n,b;
int dn=0;
bool cmp(element a,element b)
{
    if(strcmp(a.str1,b.str1)==0)return a.quality>b.quality;
    else return (strcmp(a.str1,b.str1)<0);
}

bool judge(int mid)
{
    int i,j,tmin;
    int sum=0;
    for(i=0; i<dn; i++)
    {
        tmin=1000000001;
        for(j=componets[i]; j<componets[i+1]; j++)
        {
            if(mid<=elem[j].quality)
                tmin=(tmin<elem[j].price?tmin:elem[j].price);
            else break;
        }
        if(tmin!=1000000001)sum+=tmin;
        else return false;
    }
    if(sum>b)return false;
    else return true;
}

int main()
{
    int t;

    int qmax=-1;
    int qmin=1000000001;

    cin>>t;
    while(t--)
    {

        int flag=0;
        cin>>n>>b;
        for(int i=0; i<n; i++)
        {
            scanf("%s%s%d%d",elem[i].str1,elem[i].str2,&elem[i].price,&elem[i].quality);
            qmax=(qmax>elem[i].quality?qmax:elem[i].quality);
            qmin=(qmin<elem[i].quality?qmin:elem[i].quality);
        }
        sort(elem,elem+n,cmp);
        memset(componets,0,sizeof(componets));
        dn=0;
        for(int i=1; i<n; i++)
        {
            if(strcmp(elem[i].str1,elem[i-1].str1)!=0)componets[++dn]=i;
        }
        componets[++dn]=n;

        int mid,res;
        int high,low;
        high=qmax;
        low=qmin;
        while(low<=high)                  //       ，        
        {
            mid=(low+high)>>1;
            if(judge(mid))
            {
                low=mid+1;
                res=mid;
                flag=1;
            }
            else
                high=mid-1;
        }
        if(flag)
            printf("%d
",res);
        else
            printf("0
");
    }

    return 0;
}