独自の基準でSort

競技プログラミングにおいて単なる値のみならずデータ構造をsortしたいという場面がある。
例えばpair型はそのままsortすると最初にfirstで並べ替えて次にsecondでsortするが今回は逆を基準、つまりsecondでsortした後firstでsortする。

ABC103 - D

問題

東西一列に並んだ
N個の島と N−1本の橋があります。
i番目の橋は、西からi番目の島と西からi+1番目の島を接続しています。
ある日、いくつかの島同士で争いが起こり、島の住人たちからM個の要望がありました。

要望i: 西からa_i番目の島と西からb_i番目の島の間で争いが起こったために、これらの島をいくつかの橋を渡って行き来できないようにしてほしいあなたは橋をいくつか取り除くことでこれらM個の要望全てを叶えることにしました。

取り除く必要のある橋の本数の最小値を求めてください。

制約

1≤ a_i < b_i ≤N

解法

制約によりbが右端の島なのは保証されるのでpairで値を持っておいてb優先で昇順sortしてb-1とbを繋ぐ橋を破壊する。bが同じうちは左端が東に進むだけなのでその破壊した橋で要望が満たされるし、bが東に進んだ時も直前に破壊した橋で間に合うならそれですませることで最小値が出る。
問題はsortだ。

実装

比較するための関数を定義してsortの第3引数に入れれば独自の基準でsortができる。

main.cpp

Copied!

# include <bits/stdc++.h>
using namespace std;

using ll = long long;
using P = pair<int, int>;

# define ALL(a) (a).begin(), (a).end()

//secondで比較
//sort(ALL(vectoe<P>), compare_by_b);
bool compare_by_b(P a, P b) {
  if(a.second != b.second) return a.second < b.second;
  else return a.first < b.first;
}

提出コード

main.cpp

Copied!

# include <bits/stdc++.h>
using namespace std;

using ll = long long;
using P = pair<int, int>;

# define rep(i, n) for (int i = 0; i < n; ++i)
# define ALL(a) (a).begin(), (a).end()

bool compare_by_b(P a, P b) {
  if(a.second != b.second) return a.second < b.second;
  else return a.first < b.first;
}

int main()
{
  int n, m;
  cin >> n >> m;
  vector<P> node(m);
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    node.emplace_back(a, b); //完全転送
  }
  sort(ALL(node), compare_by_b);
  int lastbreak = 0; //直前に破壊した橋
  int ans = 0;
  for(auto x : node) {
    int left = x.first;
    int right = x.second;
    if(lastbreak < left) lastbreak = right-1, ans++; //新しく破壊する必要があるならば新たに破壊
    else continue;
  }
  cout << ans << "\n";
  return 0;
}

今年は競技プログラミングを頑張りたい...