CF1060D Social Circle 排序

题目传送门：http://codeforces.com/problemset/problem/1060/D

题意：有$N$个人，你要让他们坐成若干个圆环。他们每个人需要坐一把椅子，左手边至少要有$l_i$个空椅子，右手边至少要有$r_i$个空椅子，问最少需要多少个椅子。$N \leq 10^5 \,,\, l_i,r_i \leq 10^9$

没有很好想，但也不难。
贪心地考虑什么样的人会坐在相邻位置会使得答案最优，一定是一个人的左手与另一个人的右手相差较小时较好，因为这样子重复利用的椅子数量更多。那么我们可以由此获得贪心策略：对左手与右手分别排序，然后求$\sum\limits_{i=1}^n max(l_i,r_i)$即可。这里$l_i$与$r_i$的搭配就相当于两个人相邻而坐。

 #include<bits/stdc++.h>
 #define MAXN 100010
 using namespace std;
 int numL[MAXN] , numR[MAXN];
 int main(){
  　　int N;
  　　cin >> N;
  　　 ; i <= N ; i++)
   　　   cin >> numL[i] >> numR[i];
  　　sort(numL +  , numL + N + );
  　　sort(numR +  , numR + N + );
  　　long long ans = N;
 　　  ; i <= N ; i++)
 　　　　　ans += max(numL[i] , numR[i]);
  　　cout << ans;
 　　 ;
 }

巴特西

CF1060D Social Circle 排序

最新文章

热门文章