1051.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 66 行

#include <stdio.h>
struct Stick{
    int length;
    int weight;
    bool flag;
};
bool compare(const Stick &a,const Stick &b){
    if (a.length<=b.length&&a.weight<=b.weight)
        return true;
    else
        return false;
}
void QuickSort(Stick a[],int low,int high){
    int i=low,j=high;
    Stick temp=a[low];
    while(i<j){
        while(i<j&&(temp.length<a[j].length||(temp.length==a[j].length&&temp.weight<=a[j].weight)))
            j--;
        if(i<j){
            a[i]=a[j];
            i++;
        }
        while(i<j&&(temp.length>a[i].length||(temp.length==a[i].length&&temp.weight>=a[i].weight)))
            i++;
        if(i<j){
            a[j]=a[i];
            j--;
        }
    }
    a[i]=temp;
    if(low<i)
        QuickSort(a,low,i-1);
    if(high>i)
        QuickSort(a,i+1,high);
}
void main()
{
    int Tgroups;
    scanf("%d",&Tgroups);
    Stick wooden[5000];
    int k=0;
    while (k<Tgroups){
        int testNum;
        scanf("%d",&testNum);
        int i;
        for(i=0;i!=testNum;++i){
            scanf("%d%d",&wooden[i].length, &wooden[i].weight);
            wooden[i].flag=true;
        }
        QuickSort(wooden,0,testNum-1);
        int minutes=0;
        for(i=0;i<testNum;i++)
            if(wooden[i].flag==true){
                Stick temp=wooden[i];
                for(int j=i+1;j!=testNum;j++)
                    if(wooden[j].flag==true&&compare(temp,wooden[j])){
                        temp=wooden[j];
                        wooden[j].flag=false;
                    }
                ++minutes;
            }
    printf("%d\n", minutes);
    k++;
    }
}