HDU1051Wooden Sticks

Wooden Sticks

http://acm.hdu.edu.cn/showproblem.php?pid=1051

#include<stdio.h>
struct stick{
int w ;
int l;
int flag;}wood[5000],temp,r[];
int n ;
//排序//
int  partition(struct stick r[],int first,int end){
int i=first,j=end;
while(i<j){
while(i<j && r[i].l<r[j].l) j--;
if(i<j){
temp.l=r[i].l;
temp.w=r[i].w;
r[i].l=r[j].l;
r[i].w=r[j].w;
r[j].l=temp.l;
r[j].w=temp.w;
}
while(i<j && wood[i].l<wood[j].l)i++;
if(i<j){
temp.l=wood[j].l;
temp.w=wood[j].w;
wood[j].l=wood[i].l;
wood[j].w=wood[i].w;
wood[i].l=temp.l;
wood[i].w=temp.w;
j--;}}
return i;}
void quicksort(struct stick r[],int first ,int end){
int pivot;
if(first<end){
pivot=partition(r,first,end);
quicksort(r,first,pivot-1);
quicksort(r,pivot+1,end);
}}

/
int main(){
    int t ,i ,j ,sum;
    scanf("%d",&t);
    while(t--){
    scanf("%d",&n);
    for(i=0;i<n;i++){
    scanf("%d%d",&wood[i].l,&wood[i].w);
    wood[i].flag=0;}
    quicksort(wood,0,n-1);
    sum=0;
/长度相等的把重量轻的放前面//
    for(i=0;i<n-1;i++){
        if(wood[i].l==wood[i+1].l && wood[i].w>wood[i+1].w){
        temp.w=wood[i].w; temp.l=wood[i].l;
        wood[i].w=wood[i+1].w; wood[i].l=wood[i+1].l;
        wood[i+1].w=temp.w; wood[i+1].l=temp.l;
        }
    }
 /对重量贪心选择/
    for(i=0;i<n;i++){
        if(wood[i].flag==0){
        temp.w=wood[i].w;
        for(j=i+1;j<n;j++){
            if(wood[j].flag==0 && wood[j].w>=temp.w){
                temp.w=wood[j].w;
                wood[j].flag=1;}}
    sum++;}
    }
    printf("%d\n",sum);
    }
return 0;}