usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

本文主要是介绍usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~

结构体排序核心：

1.结构体定义

struct Milk
{int price;int milks;
}milk[5000];

2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b；

int milkcmp(const void *va,const void *vb)
{Milk *a,*b;a=(Milk*)va;b=(Milk*)vb;if(a->price > b->price)return 1;if(a->price < b->price)return -1;return 0;
}

3.qsort函数调用（包含头文件 #include< algorithm >）

qsort(milk,M,sizeof(Milk),milkcmp);

本题用很简单的贪心，心得是贪心感觉就像猜想，不用详解了，上代码~

/*
ID: who jay
LANG: C++
TASK: milk
*/
#include<stdio.h>
#include<algorithm>
using namespace std;struct Milk
{int price;int milks;
}milk[5000];int milkcmp(const void *va,const void *vb)
{Milk *a,*b;a=(Milk*)va;b=(Milk*)vb;if(a->price > b->price)return 1;if(a->price < b->price)return -1;return 0;
}int main()
{FILE *fin  = fopen ("milk.in", "r");FILE *fout = fopen ("milk.out", "w");int N,M,i,msum,psum;while(fscanf(fin,"%d%d",&N,&M)!=EOF){msum=0;psum=0;for(i=0; i<M; i++){fscanf(fin,"%d %d",&milk[i].price,&milk[i].milks);}if(M==0||N==0){fprintf(fout,"0\n");continue;}qsort(milk,M,sizeof(Milk),milkcmp);for(i=0; i<M; i++){msum+=milk[i].milks;if(msum>=N){psum+=((milk[i].milks-(msum-N))*milk[i].price);fprintf(fout,"%d\n",psum);break;}psum+=(milk[i].milks*milk[i].price);}}return 0;
}

come on！！！

附上 qsort 使用实例：

1.对 int 数组进行排序

#include<stdio.h>
#include<algorithm>
using namespace std;//注意形参 const void * a .......之后强制转换 (int *)a........int cmp1(const void *a,const void *b)
{return (int *)a - (int *)b;
}
int cmp2(const void *a,const void *b)
{return (int *)b - (int *)a;
}int main()
{int num[10]= {1,3,5,7,9,2,4,6,8,0};int i;qsort(num,10,sizeof(num[0]),cmp1); //从小到大排序for(i=0; i<10; i++)printf("%d ",num[i]);printf("\n");qsort(num,10,sizeof(num[0]),cmp2); //从大到小排序for(i=0; i<10; i++)printf("%d ",num[i]);printf("\n");return 0;
}

2.对 char数组进行排序

#include<stdio.h>
#include<algorithm>
using namespace std;//注意形参 const void * a .......之后强制转换 (char *)a........int cmp1(const void *a,const void *b)
{return (char *)a - (char *)b;
}
int cmp2(const void *a,const void *b)
{return (char *)b - (char *)a;
}int main()
{char ch[11]= {"bcadfegihj"};int i;qsort(ch,10,sizeof(ch[0]),cmp1); //从小到大排序for(i=0; i<10; i++)printf("%c ",ch[i]);printf("\n");qsort(ch,10,sizeof(ch[0]),cmp2); //从大到小排序for(i=0; i<10; i++)printf("%c ",ch[i]);printf("\n");return 0;
}

3.对结构体二级及二级以上排序

即为本题代码~

Ps.

sort排序。

今天才知道sort这个stl的强大啊。

头文件 #include<algorithm>

1.对数组、向量、string 等的排序：

sort函数可以传两个参数或三个参数。

第一个参数是要排序的区间首地址，第二个参数是区间尾地址的下一地址。也就是说，排序的区间是[a,b)。简单来说，有一个数组int a[100]，要对从a[0]到a[99]的元素进行排序，只要写sort(a,a+100)就行了，默认的排序方式是升序。

对向量v排序也差不多，sort(v.begin(),v.end());

string类型同样如此。

如果是没有定义小于运算的数据类型，或者想改变排序的顺序，就要用到第三参数——比较函数。比较函数是一个自己定义的函数，返回值是bool型，它规定了什么样的关系才是“小于”。想把刚才的整数数组按降序排列，可以先定义一个比较函数cmp

bool cmp(int a,int b){return a>b;}

排序的时候就写sort(a,a+100,cmp);

2.对结构体排序：

定义了一个结构体node

struct node
{int a;int b;double c;
}arr[100]；

对它进行排序：先按a值升序排列，如果a值相同，再按b值降序排列，如果b还相同，就按c降序排列

bool cmp(node x,node y){
if(x.a!=y.a) return x.a
if(x.b!=y.b) return x.b>y.b;
return x.c>y.c;
}

排序时写sort(arr,a+100,cmp);

实例 hdu 2020

输入n(n<=100)个整数，按照绝对值从大到小排序后输出

代码：

#include <math.h>
#include <stdio.h>
#include<algorithm>
using namespace std;bool cmp(int a,int b)
{if (abs(a)>abs(b))return 1;return 0;
}int main()
{int n, i, x[101];while (scanf("%d", &n), n){for (i = 0 ; i < n ; i++)scanf("%d", x + i);sort(x, x+n, cmp);for (i = 0 ; i < n ; i++)printf("%d%c", x[i], (i != n - 1 ? ' ' : '\n'));}return 0;
}

这篇关于usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---