# Beginner's introduction (topic II) ranking (Part II) ----- > continuous update

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

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
} pre[25];
//Custom comparison function
bool cmp(Candidate a,Candidate b){
return false;
}
int main() {
cin>>n;
for(int i=1;i<=n;i++) {
pre[i].num = i;
}
sort(pre+1,pre+n+1,cmp);
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;
}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;
merge_sort(1,n);
//The results are the same, and then look down
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;
}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
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;
qs(1,n);
//The results are the same, and then look down
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;
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;
}


Posted by knobby2k on Wed, 13 Apr 2022 21:19:16 +0930