AOJ2331 a Way to Invite Friends

A Way to Invite Friends | Aizu Online Judge

Introduction to Programming Introduction to Algorithms and Data Structures Library of Data Structures Library of Graph Algorithms Library of Computational Geometry Library of Dynamic Programming Library of Number Theory

各友だちの，嫌がらない海に行く人数の範囲( )が与えられる．海に誘える最大人数を求める．
海に行く人数には「わたし」も含まれるので 人誘えるかは， 人で海に行くことを嫌がらない友だちの数が 人以上いるか，となるのでいもす法で累積和を取って順番に見ていった．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  int n;
  cin >> n;

  int imos[100005];
  memset(imos, 0, sizeof(imos));

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

      imos[a]++;
      imos[b+1]--;
  }

  REP(i, 1, 100005) {
      imos[i] += imos[i-1];
  }

  int ans = 0;
  rep(i, 100005) {
      if(imos[i+1] >= i) {
          ans = i;
      }
  }

  cout << ans << endl;

  return 0;
}
May 14th, 2016
250, aoj-icpc, いもす法