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;}

轉載于:https://www.cnblogs.com/zuojing1013/archive/2008/12/22/1359866.html

總結

以上是生活随笔為你收集整理的HDU1051Wooden Sticks的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。