【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っぽいなぁと思いました. コミュ力を上げて友達を増やそう.