Title Link: P1781 president of the universe - Luogu | new ecology of Computer Science Education (luogu.com.cn)

Title Description

In the earth calendar year 6036, the whole universe is ready to run for the president of the most talented person. There are n extraordinary top-notch people running for the president. Now the votes have been counted. Please figure out who can be the president.

Input format

The first line is an integer n, representing the number of people running for president.

Next, there are n lines, which are the number of votes from the first candidate to the nth candidate.

Output format

There are two lines in total. The first line is an integer m, which is the number of the president.

The second line is the votes of the people who become president.

Sample input and output

Enter #1 copy

5
98765
12365
87954
1022356
985678

Output #1 copy

4
1022356

Description / tips

The number of votes may be large, up to 100 digits.

1≤n≤20

Problem solving ideas

Since the number of votes may be large, a high-precision string should be used to store the number of votes.

Main ideas for solving problems:

First, input n strings to represent the number of votes of n people, but before sorting, you need to ensure that the length of all strings is consistent. First obtain the maximum length of these n strings, and fill "0" in front of the string that does not reach the maximum length, so that the size of the string is actually equivalent to the size of the number during sorting.

In normal practice (corresponding to AC code 1), b [] array is used to save the original array before sorting, so as to find the subscript corresponding to the corresponding element later.

z [] array is used to store "0", which is convenient to fill "0" in front of the string that does not reach the maximum length.

In the STL method (corresponding to AC code 2 and AC code 3, where AC code 3 is the final version after optimization), use the vector < pair < key, value > > ans container and sort in the container. It is more convenient to sort the key or value according to the topic requirements, and the key and value are bound in a one-to-one correspondence. When sorting the key or value, the value or key is also changing to ensure one-to-one correspondence between key and value. Therefore, the subscript corresponding to the array element can be obtained more conveniently and quickly, and there is no need to use the auxiliary array b[].

The problem solving code is attached below:

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 [] array is used to save the original array before sorting, so as to find the subscript corresponding to the corresponding element later.
	string z[n]; // Store '0'

	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int m=0;m<n;m++) // Gets the longest string length 
	{
		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"; // The string that does not reach the maximum length is preceded by "0"
	
	for(int i=0;i<n;i++)
	{
		a[i]=z[i]+a[i];
		b[i]=a[i]; // Save original array (Unsorted)
	}
	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]; // Store '0'

	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	for(int m=0;m<n;m++) // Gets the longest string length 
	{
		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"; // The string that does not reach the maximum length is preceded by "0"
	
	for(int i=0;i<n;i++)
	{
		a[i]=z[i]+a[i];
		ans.emplace_back(a[i],i+1);
	}
	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]; // Store '0'  

	for(int i=0;i<n;i++)
	{
		string s;
		cin>>s;
		ans.emplace_back(s,i+1);
	}
	for(int m=0;m<n;m++) // Gets the longest string length 
	{
		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"; // The string that does not reach the maximum length is preceded by "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;
}