A novice question brushing website recommended by a csdn boss, get started quickly! Luogu

Novice entry brush questions (topic II) sorting

4.12

Cosmic president

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.

sample input

5	//Number of participants
98765	//The number of votes may be large, up to 100 digits.
12365
87954
1022356
985678

sample output

4
1022356

thinking

The number of votes in this question is stored in string. When comparing, compare the length of the ticket first. If the length is the same, compare the size.

code

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct Candidate {
    int num;//Serial number
    string grade;//Number of votes
} pre[25];
//Custom comparison function
bool cmp(Candidate a,Candidate b){
    if(a.grade.length()>b.grade.length()) return a.grade.length()>b.grade.length();
    else if(a.grade.length()==b.grade.length()) return a.grade>b.grade;
    return false;
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>pre[i].grade;
        pre[i].num = i;
    }
    sort(pre+1,pre+n+1,cmp);
    cout<<pre[1].num<<endl<<pre[1].grade;
    return 0;
}

[USACO07DEC]Bookshelf B

Title Description

Slightly, ask at least a few cows to reach the height of the bookshelf

sample input

6 40	//The number of cows is 6 and the bookshelf is 40 high
6	//Height of the first cow
18
11
13
19
11

sample output

3

thinking

First quickly row the height of all cows, and then add them from large to small until > = bookshelf height, and count the added number of cows

code

#include <iostream>
#include<algorithm>
using namespace std;
int n,b,h[20020],t,k;
//Remember to quickly arrange the template
int qs(int q[],int l,int r){
    if(l>=r) return q[l];
    int i = l-1,j = r+1, x = q[l+r>>1];
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    qs(q, l, j);
    qs(q, j + 1, r);
}
int main() {
    cin>>n>>b;
    for(int i=0;i<n;i++) cin>>h[i];
    qs(h,0,n-1);
    while(t<b&&k<n){
        t += h[n-1-k];
        k++;
    }
    cout<<k;
    return 0;
}

Carriage reorganization

Title Description

Good guy, it's OK to check the bubbles.

code

#include <iostream>
#include<algorithm>
using namespace std;
int n,t[10010],times;
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&t[i]);
    }
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(t[i]>t[j]) {
                swap(t[i],t[j]);
                times++;
            }
        }
    }
    printf("%d",times);
    return 0;
}

Happy jump

Title Description

An integer array containing n elements. If the absolute value of the difference between two consecutive elements of the array includes all integers between [1,n-1], it is called "happy jump". For example, the array {1, 4, 2, 3} conforms to "happy jump", because the absolute values of the difference are: 3, 2, 1.

Given an array, your task is to determine whether the array meets the "happy jump".

sample input

5 1 4 2 -1 6	//The first number represents the length of the array, followed by each number

sample output

jolly	//Conform to "happy jump" output
Not jolly	//Does not match the "happy jump" output

thinking

Array length n (1 ≤ n ≤ 1000)

Number range in array [-10000000001000000]

This problem provides two solutions

The first method uses the difference between two numbers in barrels, that is, the difference between two numbers is stored in the way of array subscript, but the length of the array should be greater than 100000000.

It only needs that all the numbers within the array range [1,n-1] are 1, that is, it conforms to the "happy jump". See code 1 for details.

In the second method, we can study the topic. Obviously, the difference between two numbers can be calculated in the process of saving the array. Once the difference between two numbers repeats, it must not meet the "happy jump". See code 2 for details.

Code one

#include <iostream>
#include<algorithm>
using namespace std;
int n,t[1010],num[200000000];
int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&t[i]);
    }
    //bucket
    for(int i=0;i<n-1;i++){
        int tmp;
        tmp = t[i]>=t[i+1]?t[i]-t[i+1]:t[i+1]-t[i];
        num[tmp]++;
    }
    for(int i=1;i<n;i++){
        if(num[i]==0){
            printf("Not jolly");
            return 0;
        }
    }
    printf("Jolly");
    return 0;
}

Code two

#include <iostream>
using namespace std;
int n,a,b,c;
bool d[1010];
int main() {
    //Enter array length
    scanf("%d",&n);
    //Enter the first number
    scanf("%d",&a);
    //Enter from the second number
    for(int i=1;i<n;i++){
        scanf("%d",&b);
        //Calculate the difference between two numbers
        c = a>=b?a-b:b-a;
        //If the difference between the two numbers is not within [1,n-1], it must be inconsistent
        if(c>=1&&c<=n-1){
            //Judge whether it is repeated, and repetition must be inconsistent
            if(d[c]) {
                printf("Not jolly");
                return 0;
            }
            //If not repeated, continue
            else d[c] = true;
        }else {
            printf("Not jolly");
            return 0;
        }
        //Assign the second number to the first number and start the next cycle
        a = b;
    }
    //If the input cycle can be completed, it must meet the requirements
    printf("Jolly");
    return 0;
}

4.13

[NOIP2009 popularization group] score line delimitation

Title Description

The selection of Expo volunteers is in full swing in city A. In order to select the most suitable talents, city a has conducted a written test for all the applicants. Only those whose written test scores reach the interview score line can enter the interview. The interview score line is drawn according to 150% of the planned enrollment, that is, if m volunteers are planned to be admitted, the interview score line is ranked m × The scores of 150% (rounded down) contestants, and the contestants who finally enter the interview are all those whose written test scores are not lower than the interview score line.

Now please write a program to delimit the interview score line, and output the registration number and written test results of all contestants who enter the interview.

sample input

6 3 //Total number of contestants enrolled in the written examination number of volunteers enrolled in the plan
1000 90 //Contestant's registration number and contestant's written test result
3239 88 
2390 95 
7231 84 
1005 95 
1001 88

sample output

88 5 
1005 95 
2390 95 
1000 90 
1001 88 
3239 88 
//Output according to the written examination results from high to low. If the results are the same, output according to the order of registration number from small to large.

Description / tips

[example description]

m × 150%=3 × 150% = 4.5, rounded down to 4. The score line for 4 people to enter the interview is 88, but because 88 has heavy scores, all players with scores greater than or equal to 88 can enter the interview, so 5 people finally enter the interview.

thinking

Learn new sorting, merge sorting, time complexity nlogn, stability!!!

The time complexity of fast scheduling is nlogn, but it is unstable. If the problem is output according to the input order when the scores are the same, it is not appropriate to use fast scheduling, because instability will lead to the same scores but the output order is inconsistent with the input order

However, this question requires to output from small to large according to the number according to the result from large to small and the result is the same. Therefore, fast sorting and merging sorting can be used

Merge sort template

const int N=1e6+10;
int q[N],temp[N];
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        //positive sequence
        if (q[i] <= q[j]) tmp[k++] = q[i++];
    	//Reverse order	
   	    //if (q[i] >= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for (int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

Using merge sort problem solving code

#include<iostream>
using namespace std;
struct Emp{
    int num;
    int grade;
}emp[5050],tmp[5050];
int n,m;
//Modify according to the merge and sort template, stable
void merge_sort(int l, int r)
{
    if (l >= r) return;
    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        //Grades from big to small
        if (emp[i].grade > emp[j].grade) tmp[k++] = emp[i++];
    	//The results are the same, and the number is from small to large
        else if (emp[i].grade == emp[j].grade && emp[i].num <= emp[j].num) tmp[k++] = emp[i++];
        else tmp[k++] = emp[j++];
    while (i <= mid) tmp[k++] = emp[i++];
    while (j <= r) tmp[k++] = emp[j++];
    for (int i = l, j = 0; i <= r; i++, j++) emp[i] = tmp[j];
}
int main(){
    scanf("%d%d",&n,&m);
    m = m * 1.5;
    for(int i=1;i<=n;i++) scanf("%d%d",&emp[i].num,&emp[i].grade);
    merge_sort(1,n);
    //The results are the same, and then look down
    while(emp[m].grade==emp[++m].grade);
    printf("%d %d\n",emp[m].grade,--m);
    for(int i=1;i<=m;i++) printf("%d %d\n",emp[i].num,emp[i].grade);
    return 0;
}

Using fast problem solving code

#include<iostream>
using namespace std;
struct Emp{
    int num;
    int grade;
}emp[5050];
int n,m;
//Rewrite quick row
void qs(int l,int r){
    if(l>=r) return;
    int i = l-1, j = r+1, x = emp[(r+l)>>1].grade, y = emp[(r+l)>>1].num;
    while(i<j){
        //The grades are the same from large to small, and the number is from small to large
        do i++;while(emp[i].grade>x||(emp[i].grade==x&&emp[i].num<y));
        do j--;while(emp[j].grade<x||(emp[j].grade==x&&emp[j].num>y));
        if(i<j) swap(emp[i],emp[j]);
    }
    qs(l,j);
    qs(j+1,r);
}
int main(){
    scanf("%d%d",&n,&m);
    m = m * 1.5;
    for(int i=1;i<=n;i++) scanf("%d%d",&emp[i].num,&emp[i].grade);
    qs(1,n);
    //The results are the same, and then look down
    while(emp[m].grade==emp[++m].grade);
    printf("%d %d\n",emp[m].grade,--m);
    for(int i=1;i<=m;i++) printf("%d %d\n",emp[i].num,emp[i].grade);
    return 0;
}

Scrambler

Title Description

After HKE finished GDOI, he went hiking with his friends.

He marked N points on the topographic map, and each point Pi has a coordinate (xi,yi,zi). In all point pairs, the height value z will not be equal. HKE is ready to climb from the lowest point to the highest point. His climbing meets the following conditions:

(1) Through every point he marked;

(2) Starting from the second point, the height z of each point he passes is higher than the previous point;

(3) HKE can fly. The distance he climbs from one point Pi to Pj is the Euclidean distance of two points. That is,
( X i − X j ) 2 + ( Y i − Y j ) 2 + ( Z i − Z j ) 2 \sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2+(Z_i-Z_j)^2} (Xi​−Xj​)2+(Yi​−Yj​)2+(Zi​−Zj​)2 ​
Now, HKE hopes you can find out the total distance he climbs.

sample input

5	//Number of points
2 2 2	//x y z
1 1 1
4 4 4
3 3 3
5 5 5

sample output

6.928

Description / tips

[example description]

For 100% data, 1 ≤ N ≤ 50000, the range of answers is in the double range.

thinking

First sort according to the z axis, and then calculate the distance between two points

code

#include<iostream>
#include<math.h>
#include<cmath>
#include<algorithm>
using namespace std;
double ans;
struct Node { 
    int x,y,z; 
    //Heavy load<
    bool operator < (const Node &b)const{
		return z<b.z;
	}
} a[50050];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a,a+n);
    for(int i=1;i<n;i++) ans+=sqrt(pow(a[i].x-a[i-1].x,2)+pow(a[i].y-a[i-1].y,2)+pow(a[i].z-a[i-1].z,2));
    printf("%.3lf",ans);
    return 0;
}