【寒假每日一题】luogu P1781宇宙总统

寒假每日一题】luogu P1781宇宙总统"/>

【寒假每日一题】luogu P1781宇宙总统

题目链接：P1781 宇宙总统 - 洛谷 | 计算机科学教育新生态 (luogu)

题目描述

地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 n 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。

输入格式

第一行为一个整数 n，代表竞选总统的人数。

接下来有 n 行，分别为第一个候选人到第 n 个候选人的票数。

输出格式

共两行，第一行是一个整数 m，为当上总统的人的号数。

第二行是当上总统的人的选票。

输入输出样例

输入 #1复制

5
98765
12365
87954
1022356
985678

输出 #1复制

4
1022356

说明/提示

票数可能会很大，可能会到 100 位数字。

1≤n≤20

解题思路

由于票数位数可能会很大，故此题需采用高精度字符串来存放票数。

解题主要思路：

首先输入n个字符串表示n个人的票数，但在进行排序之前需要保证所有字符串长度保持一致，先获取这n个字符串的最大长度，没有达到最长长度的字符串前面补"0"，这样在排序时字符串的大小实际就相当于数字的大小。

在常规做法中（对应AC code 1），b[] 数组用来保存未排序之前的原数组，以便于后面找到相应元素所对应的下标。

z[]数组用来存放"0"，方便给没有达到最长长度的字符串前面补"0"。

在STL做法中（对应AC code 2 and AC code 3，其中 AC code 3 为优化后的最终版本），使用 vector<pair<key,value>> ans 容器，并在该容器中进行排序，可以更方便地根据题目要求对键key或值value进行排序，并且键key和值value是绑定的一一对应的关系。在对key或value进行排序时，value或key也在跟着变化，保证key-value一一对应。因此可以更加方便快捷的获取数组元素对应的下标，不需要再使用辅助数组b[]。

下面附上解题代码：

AC code 1：

#include<iostream>
#include<algorithm>
#include<climits>using namespace std;int main()
{const int inf = INT_MIN;int n,max=inf,t;cin>>n;string a[n];string b[n]; // b[]数组用来保存未排序之前的原数组，以便于后面找到相应元素所对应的下标。string z[n]; // 存放"0"for(int i=0;i<n;i++)cin>>a[i];for(int m=0;m<n;m++) // 获取最长的字符串长度 {t=a[m].size();if(t > max)max=t;			}for(int i=0;i<n;i++)for(int j=0;j<max-a[i].size();j++)z[i]+="0"; // 没有达到最长长度的字符串前面补"0"for(int i=0;i<n;i++){a[i]=z[i]+a[i];b[i]=a[i]; // 保存原始数组（未排序）}sort(a,a+n);for(int s=0;s<n;s++){if(b[s]==a[n-1]){cout<<s+1<<endl;cout<<a[n-1]<<endl;}}return 0;
}

AC code 2：

#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>using namespace std;int main()
{	const int inf = INT_MIN;vector<pair<string,int>> ans;int n,max=inf,t;cin>>n;string a[n];string z[n]; // 存放"0"for(int i=0;i<n;i++){cin>>a[i];}for(int m=0;m<n;m++) // 获取最长的字符串长度 {t=a[m].size();if(t > max)max=t;			}for(int i=0;i<n;i++)for(int j=0;j<max-a[i].size();j++)z[i]+="0"; // 没有达到最长长度的字符串前面补"0"for(int i=0;i<n;i++){a[i]=z[i]+a[i];ans.emplace_back(a[i],i+1); // a[i] 对应于键key, i+1 对应于值value。}sort(ans.begin(),ans.end());cout<<ans[n-1].second<<endl;cout<<ans[n-1].first<<endl;return 0;
}

AC code 3：

#include<iostream>
#include<algorithm>
#include<vector>
#include<climits>using namespace std;int main()
{	const int inf = INT_MIN;vector<pair<string,int>> ans;int n,max=inf,t;cin>>n;string z[n]; // 存放 "0"  for(int i=0;i<n;i++){string s;cin>>s;ans.emplace_back(s,i+1); // s 对应于键key, i+1 对应于值value。}for(int m=0;m<n;m++) // 获取最长的字符串长度 {t=ans[m].first.size();if(t > max)max=t;			}for(int i=0;i<n;i++)for(int j=0;j<max-ans[i].first.size();j++)z[i]+="0"; // 没有达到最长长度的字符串前面补"0"for(int i=0;i<n;i++){ans[i].first=z[i]+ans[i].first;}sort(ans.begin(),ans.end());cout<<ans[n-1].second<<endl;cout<<ans[n-1].first<<endl;return 0;
}