CSP-J/S Dig deep into the foundation to travel far - the function of the official question list of Luogu (2)

官方题单——【sort函数】Bookshelf B

Reference Code:

#include<iostream>
#include<algorithm>
using namespace std; 
int a[20005];
int main(){
  int n,b;
  cin>>n>>b;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a,a+n,greater<int>());
  int ans=0;
  while(b>0){
    b-=a[ans++];
  }
  cout<<ans;
}           

Algorithm parsing

According to the title, as long as you choose the highest cow every time, you can get the least number of cows within reach of the bookshelf. Therefore, it is sufficient to first sort all the cows from tallest to shortest, then simulate the stacked "cow towers" in order, and calculate the number of cows that will be able to milk at the specified height.

Interpretation of C++ knowledge in code

The sort function is explained in detail

1. The basic usage of sort().

In the C++ "algorithm" header there is a very common function sort(), which is used to sort all elements in a given interval, and its internal sorting algorithm is Quick Sort, and it defaults to ascending.

The basic usage is:

sort(array start position, array end position, sort method)

(If you don't write the sort method, it's the default ascending order)

For example, the following code:

int a[5]={1,9,5,3,4};
sort(a,a+5);
for(int i=0;i<5;i++){
   cout<<a[i]<<" ";
}           

The writing of the start and end positions in the sort function requires a deep understanding of the address knowledge of arrays (you can refer to Zhao Codesmith's previous article (link to 8.7)). Among them, the starting parameter "a" indicates that the starting point to be sorted is a[0], and the key parameter "a+5" indicates that the end point to be sorted is a[4].

If you want to sort the vector array, you can write something like this:

vector<int> a;
//省略为a数组输入元素
sort(a.begin(),a.begin()+5);
//对a数组前5个元素排序
sort(a.begin(),a.end());
//对a数组所有元素排序           

At the same time, sort() can also sort the char character array, and the sort order is dictionary order (i.e., alphabetical order) by default.

2. Non-ascending sorting method

★ (1) Sort in descending order

The sort() function is sorted in ascending order by default, if you want to sort the array in descending order, you can use another function in the "algorithm" library, the greater() function, which is a Boolean function that returns two numbers to compare whether the first number is less than the second number. The specific use of the sort() function can be written like this:

sort(a,a+n,greater<int>())           

★ (2) Customize the sorting method

If you don't want to memorize this function, you can also define the sorting function yourself. For example, for a function sorted in descending order:

bool cmp(int a, int b){
  return a < b;
}
sort(a, a + n, cmp);           

to sort the A array in descending order.

Custom sorting methods are also used more often in struct sorting. When a struct has too many attributes, one property needs to be sorted; Or you have multiple bases for ordering structs, and you need to define your own sorting methods. For example:

struct student{
  string name;
  int id;
  int total;
  int yuwen;
  int shuxue;
  int yingyu;
}s[100];
bool cmp(student a, student b){
  if(a.total==b.total){
    if(a.yuwen==b.yuwen)return a.id<b.id;
    else return a.yuwen>b.yuwen;
  }
  return a.total>b.total;
}
……
sort(s,s+100,cmp);           

For the student structure, the CMP sorting function is defined as follows: first sort according to the total score in ascending order, if the total score is the same, sort according to the ascending order of the language score, and if the language score is the same, sort by the student number from front to back.

Run the results