AOJ_2331
何人の友達と海にいけるか求める問題。
table[i] := i人(自分をふくめて)で海にいくとき、ついてきてくれる友達の数
table[i] + 1 >= i となるとき、i人で海にいけるから、自分を引いて(i-1)人が答え。
友達を誘うにはこんなことより、コミュニケーションが大事である。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100000; int table[MAX_N + 2]; int n; int main(){ scanf("%d", &n); for(int i = 0; i < n; i++){ int p, q; scanf("%d %d", &p, &q); int t = table[p]; for(int j = p; j <= q; j++) table[j]++; } int res = 0; for(int i = 0; i <= n + 1; i++){ if(table[i] + 1 >= i){ res = i - 1; } } printf("%d\n", res); return 0; }