[C++]ラムダ式を第3引数に持つsort()の使い方

sort(始まり, 終わり, 比較関数);

昇順，降順に並び替えのがメインです．

参考：AtCoderABC354-C

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(long long i=0; i<n; i++)
int main() {

int n;
cin >> n;
vector<int> a(n),c(n);
rep(i,n) cin >> a[i] >> c[i];

//index用の配列
//これを後に並び替える．
vector<int> is(n);
rep(i,n)is[i] =i;

sort(is.begin(),is.end(), [&](int i, int j){
  return a[i] > a[j];
});

vector<int> ans;
for(int i: is){
  if(ans.size() == 0 || c[ans.back()] > c[i]){
    ans.push_back(i);
  }
}
sort(ans.begin(), ans.end());
cout << ans.size() << endl;
for(int i : ans) cout << i+1 << ' ';
cout << endl;

  
    return 0;
}

注目してほしい所

cpp

sort(is.begin(),is.end(), [&](int i, int j){
  return a[i] > a[j];
});

解説

通常，sortは，

cpp

sort(is.begin(),is.end())

で配列を昇順で並べることができます．
しかしsort()は第三引数を取ることができ，その一つが，ラムダ式です．
ラムダ式とは，その場で定義した簡易的な関数のことです．

ここでは，a[i]とa[j]を比較して，a[i]が大きければtrueを返すという関数になっています．
この関数を第三引数に指定しているということは，配列aの大きさを昇順にsortしたときのindex（ここでは配列is）を並べている，ということになります．

[ 具体例を用いた説明 ]
sortした後のisとそれに対応するa[i]はこうなります．

index（配列「is」）	a[i]
2	50
0	30
3	20
1	10