Codeforces #513 D

1063 ワード

http://codeforces.com/problemset/problem/1060/D
宴会を開くには、いくつかの椅子をいくつかの輪に並べてもいいです.各賓客は耻ずかしいので左手に空席があり、右手に空席があることを要求し、テーブルを並べて使う椅子が一番少なく、出力が一番少ない椅子の数を聞いた.
問題解
絵を描くと、テーブルを置く案は人の和を変えることに相当し、でたらめに変えることができるので、並べ替えて合わせて終わります.
#include 

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair pii;

int rint() {
    int n, c, sgn = 0;
    while ((c = getchar()) < '-');
    if (c == '-') n = 0, sgn = 1;
    else n = c - '0';
    while ((c = getchar()) >= '0') {
        n = 10 * n + c - '0';
    }
    return sgn ? -n : n;
}

const int N = 1e5 + 10;

int n;
int l[N], r[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        l[i] = rint();
        r[i] = rint();
    }

    ll ans = n;
    sort(l, l + n);
    sort(r, r + n);
    for (int i = 0; i < n; i++) {
        ans += max(l[i], r[i]);   
    }
    cout << ans << endl;
    return 0;
}