codeforces_D. Social Circles

http://codeforces.com/contest/1060/problem/D

题意：

n个客人，每个客人希望自己左边空li个座位，右边空ri个座位，可以形成任意个圆，问最少多少个座位。

思路：

1、问题可以看作，给每个客人gi的左边找一个合适的另一个客人gj。其之间的空座数为max(l(gi)，r(gj))。这样匹配，自然会匹配为若干个圆。

2、将l和r排序，按大小顺利依次匹配，这样的总座位数最少。

证明：假设现在l和r都递增排好序。从匹配中任意找两对，例如(a, b)，(c,d)，且a!=c，b!=d，将其换为(c, b)，(a, d)。

1)当c<=b时，已知a<c和b<d，得a<c<=b<d，交换后，max(a, b)==max(c, b)==b，max(c, d)==max(a, d)==d

2)当c>b时，

2.1）c<=d。得a<c，b<c，c<=d。max(a, b)<max(c, b)，max(c, d)==max(a, d)

2.2）c>d。得b<d<c，a<c。max(c, d)==max(c, b)，max(a, b) 不可能大于 max(a, d)

证得，交换l序列中任意两个不同得数，总座位数不会减少。

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

#define LL long long

int main()

{

    int n,l[],r[];

    while(scanf("%d",&n)!=EOF)

    {

        for(int i=;i<n;i++)

            scanf("%d%d",&l[i],&r[i]);

        sort(l,l+n);

        sort(r,r+n);

        LL res=n;

        for(int i=;i<n;i++)

            res+=max(l[i],r[i]);

        printf("%I64d\n",res);

    }

    return ;

}

巴特西

codeforces_D. Social Circles

最新文章

热门文章