日々精進

aikoと旅行とプログラミング

【AOJ 2331】A Way to Invite Friends

問題

A Way to Invite Friends | Aizu Online Judge

方針1

  • 配列の[a, b]を++していく. 配列fをf[i]:=i人誘う時行くことができる友達の数とする.
  • i-1(自分を抜いた数)誘うときに, i - 1 <= f[i]となればi-1人誘えるということになる.

方針2

  • aのときにf[a]を1増やし, bのときf[b]を1減らす.
  • iを2から増やしつつ配列の値の総和を出し, i以上になったとき誘える人数.

コード(方針1)

#include <iostream>

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,a,n) for(int i = a ; i < (int)n ; i++)

int f[100005];

signed main(){
  int n;
  int a, b;
  cin >> n;
  rep(i, n){
    cin >> a >> b;

    REP(j,a,(b+1)){
      f[j]++;
    }
  }

  int idx = 0;
  REP(i, 2, 100002){
    if(i-1 <= f[i]){
      idx = i-1;
    }
  }
  
  cout << idx << endl;
}

コード(方針2)

#include <iostream>

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,a,n) for(int i = a ; i < (int)n ; i++)

int f[100005];

signed main(){
  int n;
  int a, b;
  cin >> n;
  rep(i, n){
    cin >> a >> b;
    f[a]++;
    f[b + 1]--;
  }
  
  int sum = 1;
  int idx = 0;
  rep(i, 100002){   // i人誘う
    sum += f[i];
    if(i <= sum){   // n人中sum人が行くことができる. i<=sumを満たしてればよい
      idx = i;
    }
  }
  
  idx--;
  cout << idx << endl;
}

2の方, なんかimosっぽいなぁと思いました. コミュ力を上げて友達を増やそう.