洛谷【算法1-2】排序

车厢重组

题目描述

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 $180$ 度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

输入格式

共两行。

第一行是车厢总数 N( <= 10000)。

第二行是 N 个不同的数表示初始的车厢顺序。

输出格式

一个整数，最少的旋转次数。

样例 #1

样例输入 #1

4
4 3 2 1

样例输出 #1

6

提示

题解：

这是一个冒泡排序，直接写算法就行了,n个数，共需要n-1次排序，加了一个flag判断，排好序就结束。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int a[10000+5];
int n;
int cnt;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n-1;i++)
    {
        int flag=0;
        for(int j=0;j<n-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
                cnt++;
                flag=1;
            }
        }
        if(flag==0)break;
    }
    cout<<cnt<<endl;
}

欢乐的跳

题目描述

一个 n 个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了 [1,n-1] 之间的所有整数，则称之符合“欢乐的跳”，如数组 {1,4,2,3} 符合“欢乐的跳”，因为差的绝对值分别为：3,2,1。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

输入格式

每组测试数据第一行以一个整数 n(1 <= n <= 1000) 开始，接下来 n 个空格隔开的在 [-10^8,10^8] 之间的整数。

输出格式

对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出 Jolly，否则输出 Not jolly。

样例 #1

样例输入 #1

4 1 4 2 3

样例输出 #1

Jolly

样例 #2

样例输入 #2

5 1 4 2 -1 6

样例输出 #2

Not jolly

提示

1 <= n <= 1000

60分题解：

先输入之后，用一个bool数组，将输入的数差的绝对值当成下标，但是只获得了60分的分数，原因在于，当两个数相差过大时，会发生数组的越界。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int n;
int a[1005];
bool vis[1005];
int main()
{
    cin>>n;
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
   }
   for(int i=0;i<n-1;i++)
   {
       vis[abs(a[i]-a[i+1])]=true;
   }
   for(int i=1;i<n;i++)
   {
       if(!vis[i])
       {
           cout<<"Not jolly"<<endl;
           return 0;
       }
   }
   cout<<"Jolly"<<endl;
   return 0;
}

题解：

思考之后，可以将这个相差的数存起来，然后用sort排序去比较，或者把数组开大一些。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int n;
int a[1005];
int vis[1005];
int main()
{
    cin>>n;
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
   }
   for(int i=0;i<n-1;i++)
   {
       vis[i]=abs(a[i]-a[i+1]);

   }
   sort(vis,vis+n-1);

   for(int i=1;i<n;i++)
   {
       if(vis[i-1]!=i)
       {
           cout<<"Not jolly"<<endl;
           return 0;
       }
   }
   cout<<"Jolly"<<endl;
   return 0;
}

[USACO07DEC]Bookshelf B

题目描述

Farmer John最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。

所有 N(1 <=N <= 20,000)$ 头奶牛都有一个确定的身高 H_i(1 <= H_i <= 10,000)。设所有奶牛身高的和为S。书架的高度为B，并且保证 1 <= B <= S < 2,000,000,007。

为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。

显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。 现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。

输入格式

• 第 1 行: 2 个用空格隔开的整数：N 和 B；
• 第 2… N+1 行: 第 $i+1$ 行是 1 个整数：H_i。

输出格式

• 第 1 行: 输出 1 个整数，即最少要多少头奶牛叠成塔，才能够到书架顶部

样例 #1

样例输入 #1

6 40
6
18
11
13
19
11

样例输出 #1

3

提示

输入说明:

一共有 6 头奶牛，书架的高度为 40，奶牛们的身高在 6…19之间。

输出说明:

一种只用 3 头奶牛就达到高度 40 的方法：18+11+13。当然还有其他方法，在此不一一列出了。

题解：

直接用sort排序，从小到大取就行了。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int N,B;
int a[20000+5];
int cnt;
int sum;
int main()
{
   cin>>N>>B;
   for(int i=0;i<N;i++)
   {
       cin>>a[i];
   }
   sort(a,a+N);
   while(sum<B)
   {
       sum+=a[N-cnt++];
   }
   cout<<cnt-1<<endl;
}

[NOIP2009 普及组] 分数线划定

题目描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 150% 划定，即如果计划录取 m 名志愿者，则面试分数线为排名第 m x 150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

输入格式

第一行，两个整数 $n,m(5 <= n <= 5000,3 <= m <= n)，中间用一个空格隔开，其中 $n$ 表示报名参加笔试的选手总数，$m$ 表示计划录取的志愿者人数。输入数据保证 $m \times 150%$ 向下取整后小于等于 n。

第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号 k(1000 <= k <= 9999)$和该选手的笔试成绩 s(1 <= s
<= 100)。数据保证选手的报名号各不相同。

输出格式

第一行，有 2 个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。

从第二行开始，每行包含 2 个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

样例 #1

样例输入 #1

6 3 
1000 90 
3239 88 
2390 95 
7231 84 
1005 95 
1001 88

样例输出 #1

88 5 
1005 95 
2390 95 
1000 90 
1001 88 
3239 88

提示

【样例说明】

m x 150 = 3 x 150 = 4.5，向下取整后为 4。保证 4 个人进入面试的分数线为 88，但因为 88 有重分，所以所有成绩大于等于 88 的选手都可以进入面试，故最终有 5 个人进入面试。

NOIP 2009 普及组 第二题

题解：

先用结构体赋值，容易排序，排序之后，注意要判断有几个人入选，这里是用分数判断的，所以不能用m*150%向下取整，要先循环一遍，判断有多少个重复的值，再输出。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int n,m;
struct person
{
    int id;
    int num;
}p[10000];
bool cmp(person p1,person p2)
{
    if(p1.num==p2.num)
        return p1.id<p2.id;
    return p1.num>p2.num;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].id>>p[i].num;
    }
    sort(p+1,p+n+1,cmp);
    int a=1.5*m;
    int cnt=a;
    while(1)
    {
        if(p[cnt].num>=p[a].num)
            cnt++;
        else
            break;
    }

    cout<<p[int (m*1.5)].num<<" "<<cnt-1<<endl;
    for(int i=1;i<cnt;i++)
    {
        cout<<p[i].id<<" "<<p[i].num<<endl;
    }
    return 0;
}

攀爬者

题目背景

HKE 考完 GDOI 之后跟他的神犇小伙伴们一起去爬山。

题目描述

他在地形图上标记了 N 个点，每个点 P_i 都有一个坐标 (x_i,y_i,z_i)。所有点对中，高度值 z 不会相等。HKE 准备从最低的点爬到最高的点，他的攀爬满足以下条件：

(1) 经过他标记的每一个点；

(2) 从第二个点开始，他经过的每一个点高度 $z$ 都比上一个点高；

(3) HKE 会飞，他从一个点 P_i 爬到 P_j 的距离为两个点的欧几里得距离。即，sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2+(Z_i-Z_j)^2}

现在，HKE 希望你能求出他攀爬的总距离。

输入格式

第一行，一个整数 N 表示地图上的点数。

接下来 N 行，三个整数 x_i,y_i,z_i 表示第 i 个点的坐标。

输出格式

一个实数，表示 HKE 需要攀爬的总距离（保留三位小数）

样例 #1

样例输入 #1

5
2 2 2
1 1 1
4 4 4
3 3 3
5 5 5

样例输出 #1

6.928

提示

对于100%的数据，1<= N<= 50000，答案的范围在 double 范围内。

题解：

先用结构体定义，然后用sort排序，最后直接相加就行，保留三位小数用C语言中的printf比较方便。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct xyz
{
    int x;
    int y;
    int z;
}a[50000+10];
int n;
double sum;
bool cmp(xyz a1,xyz a2)
{
    return a1.z<a2.z;
}
int s1,s2,s3;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].z;
    }
    sort(a,a+n,cmp);
    for(int i=1;i<n;i++)
    {
        s1=a[i].x-a[i-1].x;
        s2=a[i].y-a[i-1].y;
        s3=a[i].z-a[i-1].z;
        sum+=sqrt(s1*s1+s2*s2+s3*s3);
    }
    printf("%.3lf",sum);
}

[NOIP1998 提高组] 拼数

题目描述

设有 n 个正整数 a_1 … a_n，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 n。

第二行有 n 个整数，表示给出的 n 个整数 a_i。

输出格式

一个正整数，表示最大的整数

样例 #1

样例输入 #1

3
13 312 343

样例输出 #1

34331213

样例 #2

样例输入 #2

4
7 13 4 246

样例输出 #2

7424613

提示

对于全部的测试点，保证 1 <= n <= 20，1 <= a_i <= 10^9。

题解：

这个题要把每个数最高位相比较，如果用Int去存数的话，比较的时候麻烦，所以用字符串来存，比较字符第一个字符。直接比较a和b的话。如果相同会报错，比如321和32，会输出32132而不是32321，所以要把这俩字符串前后加起来比较。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int num=1e9+10;
int n;
string a[21];
bool cmp(string a,string b)
{
    return a+b>b+a;
}
int main()
{
   cin>>n;
   for(int i=0;i<n;i++)
    cin>>a[i];
   sort(a,a+n,cmp);
   for(int i=0;i<n;i++)
    cout<<a[i];
   return 0;
}

生日

题目描述

cjf 君想调查学校 OI 组每个同学的生日，并按照年龄从大到小的顺序排序。但 cjf 君最近作业很多，没有时间，所以请你帮她排序。

输入格式

输入共有 2 行，

第 1 行为 OI 组总人数 n；

第 2 行至第 n+1 行分别是每人的姓名 s、出生年 y、月 m、日 d。

输出格式

输出共有 n行，

即 n 个生日从大到小同学的姓名。（如果有两个同学生日相同，输入靠后的同学先输出）

样例 #1

样例输入 #1

3
Yangchu 1992 4 23
Qiujingya 1993 10 13
Luowen 1991 8 1

样例输出 #1

Luowen
Yangchu
Qiujingya

提示

数据保证，1<n<100，1<= |s|<20。保证年月日实际存在，且年份 ∈ [1960,2020]。

题解：

依旧用结构体来写，sort排序。分好cmp中，当其中的年月日相等时，怎么排大小。
结构体中加了一个id，当年月日大小相等时，用id的前后顺序去排列。

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct student
{
    int id;
    string name;
    int year;
    int month;
    int day;
}a[105];
bool cmp(student a,student b)
{
    if(a.year==b.year)
    {
        if(a.month==b.month)
        {
          if(a.day==b.day)
            return a.id>b.id;
          else
            return a.day<b.day;
        }
        else
            return a.month<b.month;
    }
    return a.year<b.year;
}
int n;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i].name>>a[i].year>>a[i].month>>a[i].day;
        a[i].id=i;
    }
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++)
    {
        cout<<a[i].name<<endl;
    }
    return 0;
}