AOJ 2331 A Way to Invite Friends
data[n]:n人誘った時に嫌がらずに許容してくれる最大人数を入れる配列を準備する。
例えば、
Aさん 3~5人まで可能
Bさん 2~3人まで可能
であれば、
data[1]=0
data[2]=1
data[3]=2
data[4]=1
data[5]=1
となるように格納する。
方法としては、友人それぞれに対してdata[a[i]]に+1,data[b[i]+1]の箇所に-1を演算し、
data[0]から更新していく。
#include <iostream> #define REP(i,n) for(int i=0;i<n;i++) using namespace std; int main(){ int n; int *a, *b; int *data; cin >> n; a = new int[n]; b = new int[n]; data = new int[100010]; REP(i, n){ cin >> a[i] >> b[i]; } REP(i, 100010){ data[i] = 0; } REP(i, n){ data[a[i]]++; data[b[i]+1]--; } int num = 0; REP(i, 100010){ num += data[i]; data[i] = num; // cout << data[i] << " "; } //cout << endl; for (int i = n + 1; i > 0; i--){ if (data[i]+1 >= i){ cout << i - 1 << endl; return 0; } } cout << 0 << endl; return 0; }