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; }