Doki Doki Literature Club（sort 函数对结构体函数的排序、结构体字符串之间的比较）

153 - The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple - L

Doki Doki Literature Club

题目链接：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5761

解题思路：可以说这道题目是比较简单的，一开始就可以想到运用结构体数组来进行存储，再用sort函数对结构体中的字符串以及幸福值排序输出就可以了。但是就是这样简单的思路，却照片男更是反复的卡，反复的出错。所以来总结一下结构体中常见的易错点，还有bool的cmp函数写法。

1.结构体数组在访问的时候：

struct node
{char str[20];long long happy;
}arr[105];for(i = 0;i < n; i++)
{scanf("%s",arr[i].str);  //这里由于访问的是数组，所以不需要取地址符,直接使用数组名就可以代表这个数组的首地址.scanf("%d",&arr[i].happy);      //而这里加了取地址符是因为这里的变量,它本身不能代表自己的地址.
}

其实结构体数组的访问取地址符问题就可以类似于一般的访问方式,相互对应着记会更容易理解.

2.sort函数来排结构体数组:

*sort函数的头文件是：#include<algorithm>

首先再说这个之前,需要特别提醒的就是,字符串的比较和变量比较的差别!!!!!!!!!(非常重要,之前很多都忽视了这个)

if(arr[i].happy == arr[j].happy)if(strcmp(arr[i].happy,arr[j].happy) > 0)    //如果是字符串比较的话,一定要用这个函数.

对于strcmp函数的返回值问题在进行讲解下:

(此处解释来自于官方的百度百科,因此我想要表达的是:大家不要误以为strcmp函数,在比较过程中的返回值正数是1.

再讲解用sort函数对结构体数组进行排序开始之前,先来看下简单的sort函数排序的方法:

#include<algorithm>  //头文件
using namespace std;bool cmp(int a,int b)
{return a > b;    
}                           //c++中默认的为升序排列,如果升序的话就不需要写这个cmp函数.int main()
{int a[205];sort(a,a + n,cmp);  //sort函数的三个参数:数组的起始地址,结束地址(最后一位要排序的地址的下一位),排序的方法

下面sort函数对结构体数组的排序:

#include<algorithm>
using namespace std;struct node
{char str[20];long long happy;
}arr[105];bool cmp(node a,node b)
{if(a.happy == b.happy){if(strcmp(a.str,b.str) > 0)return a.str < b.str;elsereturn a.str > b.str;}elsereturn a.happy > b.happy;
}int main()	sort(arr,arr + n,cmp);
{for(i = 0;i < n; i++){scanf("%s",arr[i].str);scanf("%d",&arr[i].happy);}		

最后总的代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{char str[20];long long int happy;
}arr[105];
bool cmp(node a,node b)
{if(a.happy == b.happy){if(strcmp(a.str,b.str) > 0)return a.str < b.str;elsereturn a.str > b.str;}else return a.happy > b.happy; 
}
int main()
{int n;scanf("%d",&n);while(n--){int i,m,a;long long ans = 0;scanf("%d %d",&m,&a);for(i = 1;i <= m; i++){scanf("%s",arr[i].str);scanf("%lld",&arr[i].happy);}sort(arr + 1,arr + 1 + m,cmp);for(i = 1;i <= a; i++){ans += (a - i + 1) * arr[i].happy;}printf("%lld ",ans);                //这里一定要开long long for(i = 1;i <= a; i++){if(i == a)printf("%s\n",arr[i].str);elseprintf("%s ",arr[i].str);}}return 0;
}

*初级练习sort函数排列结构体题目推荐：

        poj小白鼠排队