ACM程序设计课内实验（2）排序问题

小鱼儿 2024-04-17 13:41 64阅读 0赞

## 基础知识‘ ##

> sort函数
> 
> C++中的sort函数是库中的一个函数，用于对容器中的元素进行排序。它的原型如下：
> 
>     template <class RandomAccessIterator, class Compare>
>     void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
> 
>     参数说明：
> 
>  *  first：指向要排序序列的第一个元素的迭代器。
>  *  last：指向要排序序列的最后一个元素的下一个位置的迭代器。
>  *  comp：一个比较函数，用于指定排序的顺序。默认情况下，它使用operator<进行升序排序。如果需要降序排序，可以提供一个自定义的比较函数。![4575b722b85f4935a3e76e5b9fec3da4.png][]
> 
> qsort函数
> 
> C++中的qsort函数是一个通用的排序函数，它位于头文件中。qsort函数接受一个数组、数组的大小以及一个比较函数作为参数。比较函数用于确定数组中元素的顺序。
> 
>     #include <cstdlib>
>     #include <iostream>
>     #include <algorithm>
>     
>     using namespace std;
>     
>     //定义比较函数，用于排序
>     int cmp(const void *a, const void *b)
>     {
>         int *pa=(int *)a;
>         int *pb=(int *)b;
>         
>         return *pa-*pb;
>     }
>     
>     int main()
>     {
>         int arr[]={10, 8, 2, 6, 7, 3};
>         int len=sizeof(arr)/sizeof(arr[0]);
>     
>         qsort(arr, len, sizeof(int), cmp);
>         
>         for(int i=0;i<len;i++)
>         {
>             cout<<arr[i]<<" ";
>         }
>         
>         return 0;
>     }

## 1.排序 ##

> #### Description ####
> 
>     给你很多行数，将每行数排序（从小到大）！
> 
> #### Input ####
> 
>     输入数据有很多行，每行10个正整数。
> 
> #### Output ####
> 
>     将每行数从小到大输出。
> 
> #### Sample Input ####
> 
>     10 9 8 7 6 5 4 3 2 1
> 
> #### Sample Output ####
> 
>     1 2 3 4 5 6 7 8 9 10

#include <iostream>
    #include <sstream>
    #include <algorithm>
    
    using namespace std;
    
    // 快速排序函数，arr为待排序数组，left为左边界，right为右边界
    void quickSort(int arr[], int left, int right) {
        if (left < right) {
            int pivot = arr[left]; // 选择基准值
            int i = left; // 左指针
            int j = right; // 右指针
            while (i < j) {
                // 从右向左找到第一个小于基准值的元素
                while (i < j && arr[j] >= pivot) {
                    j--;
                }
                // 如果找到了，将其与左指针指向的元素交换，并将左指针向右移动一位
                if (i < j) {
                    arr[i++] = arr[j];
                }
                // 从左向右找到第一个大于基准值的元素
                while (i < j && arr[i] < pivot) {
                    i++;
                }
                // 如果找到了，将其与右指针指向的元素交换，并将右指针向左移动一位
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }
            // 将基准值放到正确的位置上
            arr[i] = pivot;
            // 递归地对左右两部分进行快速排序
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }
    
    int main() {
        int arr[100];
        while(scanf("%d",&arr[0])!=EOF){ 
    
            for(int i=1; i<10; i++) 
                scanf("%d",&arr[i]);
            quickSort(arr, 0, 9);
            for (int i = 0; i < 10; i++) { 
                cout << arr[i] << " ";
            }
            cout << endl; 
        }
        return 0;
    }

## 2.枫之舞------排序 ##

> #### Description ####
> 
>     你会排序吗？请将给出的数据按（升序）排序~~
> 
> #### Input ####
> 
>     输入数据有多组，首先输入一个T，代表有T组数，然后是T行，每行开头是N,代表有N个数需要排序，然后就是这N个要排序的数了！N大于1且小于1000.
> 
> #### Output ####
> 
>     把数据从小到大排序。
> 
> #### Sample Input ####
> 
>     2
>     3 2 1 3
>     9 1 4 7 2 5 8 3 6 9
> 
> #### Sample Output ####
> 
>     1 2 3
>     1 2 3 4 5 6 7 8 9

#include <bits/stdc++.h>
    using namespace std;
    int x[1005];
    int main()
    {
        int t;
        cin>>t;
        while(t--)
        {
            int n;
            cin>>n;
            for(int i=0;i<n;i++)
                scanf("%d",&x[i]);
            sort(x,x+n,less<int>());
            for(int i=0;i<n-1;i++)
                printf("%d ",x[i]);
            printf("%d",x[n-1]);
            printf("\n");
        }
        return 0;
    }

## 3.让气球飞吧 ##

> #### Description ####
> 
>     国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛，ACM-ICPC以团队的形式代表各学校参赛，每队由3名队员组成，一个队每做出来一个题该队就会获得该题对应颜色的气球，气球越多就说明该队做的题目越多。当然如果一个颜色的气球越多就说明该气球对应的题也就越简单。现在给你很多很多的颜色的气球，问你那个颜色的气球最多，哈哈，聪明的acmer这题对你肯定很简单吧， just ac it！
> 
> #### Input ####
> 
>     假设只有6种颜色，green，red，blue，pink，orange，black。输入数据有多组，每组数据开始给出一个整数n代表接下来有n个气球，接下来有n行，每行输入一种颜色，n <= 100,输入以EOF结束。
> 
> #### Output ####
> 
>     输出个数最多的气球的颜色（题目保证个数最多的气球有且仅有一种颜色）
> 
> #### Sample Input ####
> 
>     3
>     green
>     red
>     green
>     5
>     green
>     red
>     blue
>     red
>     red
> 
> #### Sample Output ####
> 
>     green
>     red

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    int main()
    {
        char b[6][10]= {"red","green","blue","pink","black","orange"};
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            int res[6]= {0};
            int k;
            for(k=0; k<n; k++)
            {
                char a[10];
                scanf("%s",a);
                int i;
                for(i=0; i<6; i++)
                {
                    if(strcmp(b[i],a)==0)
                        res[i]++;
                }
            }
            int num=0,max=res[0];
            int j;
            for(j=1; j<6; j++)
            {
                if(max<res[j])
                {
                    max=res[j];
                    num=j;
                }
            }
            printf("%s\n",b[num]);
        }
        return 0;
    }

改进

#include <iostream>
    #include <map>
    #include <string>
    using namespace std;
    
    int main() {
        int n;
        string color;
        map<string, int> color_count;
    
        while (scanf("%d",&n)!=EOF) {
            color_count.clear();
            for (int i = 0; i < n; i++) {
                cin>>color;
                color_count[color]++;
            }
            string max_color = "";
            int max_count = 0;
            for (const auto &p : color_count) {
                if (p.second > max_count) {
                    max_count = p.second;
                    max_color = p.first;
                }
            }
    
            cout << max_color << endl;
    
        }
    
    
        return 0;
    }

## 4.Google is Feeling Lucky ##

> #### 描述 ####
> 
> 谷歌是最著名的互联网搜索引擎之一，它托管和开发了许多基于互联网的服务和产品。在其搜索引擎网站上，一个有趣的按钮“我感觉很幸运”吸引了我们的眼球。该功能可以允许用户跳过搜索结果页面，直接进入排名第一的页面。
> 
>   
> 太神了它节省了很多时间。
> 
>   
> 问题是，当一个人键入一些关键词并按下“我感觉很幸运”按钮时，会出现哪个网页？谷歌做了很多工作，并提出了很好的方法来处理它。在这个简化的问题中，让我们只考虑谷歌为每个网页分配一个整数值的相关性。将选择最相关的页面。如果出现平局，则可以选择相关性最高的所有页面。
> 
>   
> 你的任务很简单，给定10个网页及其相关性。只要挑选出所有可能的候选人，当“我感到幸运”时就会提供给用户。
> 
> #### 输入 ####
> 
> 输入包含多个测试用例。测试用例的数量T在输入文件的第一行中。  
> 对于每个测试用例，有10行描述网页和相关性。每一行都包含一个字符串，没有任何空白字符表示该网页的URL，以及一个整数Vi表示该网页相关性。URL的长度介于1和100之间（包括1和100）。（1<=Vi<=100）
> 
> #### 输出 ####
> 
> 对于每个测试用例，输出几行，这些行是可以选择的网页的URL。URL的顺序与输入的顺序相同。  
> 有关输出格式的更多信息，请查看示例输出。
> 
> #### 样本输入 ####
> 
> 2  
> www.youtube.com 1  
> www.google.com 2  
> www.google.com.hk 3  
> www.alibaba.com 10  
> www.taobao.com 5  
> www.bad.com 10  
> www.good.com 7  
> www.fudan.edu.cn 8  
> www.university.edu.cn 9  
> acm.university.edu.cn 10
> 
>   
> www.youtube.com 1  
> www.google.com 2  
> www.google.com.hk 3  
> www.alibaba.com 11  
> www.taobao.com 5  
> www.bad.com 10  
> www.good.com 7  
> www.fudan.edu.cn 8  
> www.university.edu.cn 9  
> acm.university.edu.cn 10
> 
> ####   
 样本输出 ####
> 
> 案例1：  
> www.alibaba.com  
> www.bad.com  
> acm.university.edu.cn  
> 案例2：  
> www.alibaba.com

方法一

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        int t;
        cin>>t;
        int n=1;
        while(t--)
        {
            char ch[12][120];
            int num[12];
            for(int i=1; i<=10; i++)
                cin>>ch[i]>>num[i];
            int maxn=-999999;
            for(int i=1; i<=10; i++)
            {
                if(num[i]>maxn)
                    maxn=num[i];
            }
            printf("Case #%d:\n",n);
            n++;
            for(int i=1; i<=10; i++)
                if(num[i]==maxn)
                    cout<<ch[i]<<endl;
        }
        return 0;
    }

方法二

#include <iostream>
    #include <algorithm>
    #include <string>
    
    using namespace std;
    
    struct WebPage {
        string url;
        int relevance;
    };
    
    bool compare(const WebPage &a, const WebPage &b) {
        if (a.relevance == b.relevance) {
            return a.url < b.url;
        }
        return a.relevance > b.relevance;
    }
    
    int main() {
        int T;
        cin >> T;
        for (int t = 0; t < T; ++t) {
            WebPage webPages[10];
            for (int i = 0; i < 10; ++i) {
                cin >> webPages[i].url >> webPages[i].relevance;
            }
            sort(webPages, webPages + 10, compare);
            cout << "Case #" << t + 1 << ":" << endl;
            cout << webPages[0].url << endl;
            for (int i = 1; i < 10; ++i) {
                if(webPages[i].relevance == webPages[0].relevance)
                     cout << webPages[i].url << endl;
    
            }
            cout << endl;
        }
        return 0;
    }

## 5.数字排序 ##

> #### Description ####
> 
>     现在给出一个不超过1000个数字（允许重复），小新想知道其中的数字
>     是第几小的数,例如给出5 4 4 2 1，1就是第一小的数，4就是第3小的数，5
>     就是滴小的数。
> 
> #### Input ####
> 
>     多组样例。每组第一行是一个整数n,跟着n(n <= 1000)个整数(a1,a2,a3,……，an)，
>     第二行一个整数m( m < 100)表示将要询问的次数，跟着m个整数（b1,b2,b3……，bn）
> 
> #### Output ####
> 
>     对于每次询问输出一行，表示bi(i >= 1&& i <= m)是第几小的数，如果aj(j >= 1 && j <= n)中
>     不存在bj则直接输出-1.
> 
> #### Sample Input ####
> 
>     5 5 4 4 2 1
>     3 1 4 5
>     3 1 3 2
>     3 1 4 2
> 
> #### Sample Output ####
> 
>     1
>     3
>     4
>     1
>     -1
>     2

#include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    set<int> vis;
    set<int>::iterator it;
    int main()
    {
        int i,j,m,n,flag,k;
        while(cin>>n)
        {
            vis.clear();
            for(i=1;i<=n;i++)
            {
                cin>>m;
                vis.insert(m);
            }
            cin>>m;
            int p;
            for(i=1;i<=m;i++)
            {
                flag=-1;cin>>p;
                for(it=vis.begin(),k=1;it!=vis.end();it++,k++)
                {
                    if(p==*it){flag=k;break;}
                }
                cout<<flag<<endl;
            }
        }
        return 0;
    }

[4575b722b85f4935a3e76e5b9fec3da4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/12/0f8cce1e912c43f49575b287beba6151.png