介绍一个二次排序的小技巧(best coder27期1001jump jump jump)
2024-10-21 04:14:16
先来描述一下问题:
问题描述
有n小孩在比赛跳远,看谁跳的最远。每个小孩可以跳3次,这个小孩的成绩就是三次距离里面的最大值。例如,一个小孩跳3次的距离分别时10, 30和20,那么这个小孩的成绩就是30。给出每个孩子三次跳的距离,问最终每个孩子的排名是多少。 问题分析:
方法1:
由于原问题规模较少,只有两个或三个孩子,可以采用暴力的方法解决,也可满足时间在1s之内(除java代码)。 方法2:
由于该问题按孩子跳远距离的最大值进行排序的话,再次按孩子照顺序输出的时候就会出现,由于原顺序未保存而导致不正确。 解决方案:
设计新结构体存储一个孩子的三个结构信息,跳远距离,当前顺序和排序后的优先级。然后分别按照跳远距离排序,然后根据顺序更新优先级,然后再按照最初的输入顺序进行排序。
代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NUM 10 typedef struct jump_kid
{
int num;
int value;
int pri; }jump_kid; int max_of_three(int a,int b,int c)
{/*前提a!=b!=c*/
int max3;
if(a > b && a > c)
max3 = a;
else if(b > a && b > c)
max3 = b;
else
max3 = c;
return max3;
} int comp_kids_value(const void *a, const void *b)
{//value降序排序
return ( ((jump_kid *)b)->value - ((jump_kid *)a)->value );
} int comp_kids_num(const void *a, const void *b)
{
return ( ((jump_kid *)a)->num - ((jump_kid *)b)->num );
}
int main()
{
int i,j,num_case,num_kid,jump1,jump2,jump3;
jump_kid kids[MAX_NUM];
scanf("%d",&num_case); for(i = ; i <= num_case; i++)
{
memset(kids,,sizeof(kids));
scanf("%d",&num_kid);
for(j = ; j < num_kid; j++)
{
scanf("%d%d%d",&jump1,&jump2,&jump3);
kids[j].num = j + ;
kids[j].pri = ;
kids[j].value = max_of_three(jump1,jump2,jump3);
} qsort(kids,num_kid,sizeof(jump_kid),comp_kids_value); //第一遍按照value值排序 for( j = ; j < num_kid; j++)
{
kids[j].pri = j + ; //排序后更新优先级
} qsort(kids,num_kid,sizeof(jump_kid),comp_kids_num); for( j = ; j < num_kid; j++)
printf("%d ",kids[j].pri); printf("\n");
} }
最新文章
- Maven入门详解
- web页面之响应式布局
- iOS开发之窥探UICollectionViewController(三) --使用UICollectionView自定义瀑布流
- ibatis实现Iterate的使用
- TCP SYN扫描学习笔记
- jquery实现动画
- 安装DotNetCore.1.0.0-VS2015Tools.Preview2失败解决方案
- [转载] Android.Hook框架xposed开发篇
- git vs svn
- Js RegExp对象
- AngularJS中的MVC模式
- JavaScript入门介绍(二)
- Apache-Tika解析XML文档
- 转:PHP include()和require()方法的区别
- eclipse提交hadoop集群跑程序
- Hadoop: the definitive guide 第三版 拾遗 第十二章 之Hive分区表、桶
- 理解Java Integer的缓存策略【转】
- 关于伪类after后续追加,实现js事件(如点击事件)
- svg param.js的大bug
- php与html实现交互的基本操作