AGC028 C Min Cost Cycle

题目链接
题意：
给你一个有向完全图，每个点有两个权值a和b，边的边权是起点的a和终点的b的最小值，求一个权值和最小的哈密尔顿回路，输出权值和。点数1e5

题解：
记得颜神说atcoder是一个很练思维的网站，上面有很多好题，于是我打算开始刷atcoder的题目。脑子是个好东西，可惜现在的我没有。。

这道题乍一看感觉不太好想，显然没法把边建出来，更没办法枚举哈密尔顿回路。我看了官方题解，但是也不能算是完全明白了这道题。我感觉官方题解有点啰嗦，不太明白官方题解的前半部分想说什么，于是就简化一下，按照我的理解写一下题解，如果有什么错误，恳请诸位大神斧正。

首先我们考虑一个合法的解一定是有n条路径的一个环，这个环上的n条边的权值一定是这$n$n个$a_i$ai​和n个$b_i$bi​这$2n$2n个数中选出了$n$n个数组成了答案。我们考虑在所有能形成环的选择方式中，可能是最优解的有哪些情况。其中很显然有两种可能最优的但是一定能形成一个环的解是我们对于所有点都选$a_i$ai​，或者都选$b_i$bi​。这两种显然很好求答案。
另外一种情况就是有些点进来时用了它的$b_i$bi​，出去的时候边权又用了它的$a_i$ai​，而相应的，我们最后要选$n$n个值，那么有多少点$a_i$ai​和$b_i$bi​都选了，就应该对应有多少点$a_i$ai​和$b_i$bi​都没选。既然我们要回路的权值和最小，那么我们就要尽可能的优先选择权值小的边，算是用到了贪心的思想吧。我们先把所有的a和b混在一起排序，对其中的前n个数求一个前缀和。然后考虑对于每个点它a和b都选的情况下最小的权值和会不会比已经出现过的答案更优。我们为了得到可能的最优解，我们选$a_i$ai​和$b_i$bi​之后再选$n-2$n−2个权值最小的点，我们根据抽屉原理可知这时候至少一定存在一个点的$a_i$ai​和$b_i$bi​都没有选。这样都尝试更新答案之后最后的结果就是最优解了。
好，请教当场切掉这题的了lyf之后我明白了为什么这样一定是合法的。
不会证明，但是可以构造，只要a的前k个和b的前n-k个中有交就一定有解，有交的含义是存在一个点它的a和b都被选了。而我们选某一个点，让它的a和b都选，就是保证了有交，即是合法解。
构造的方法是如下：

代码：

#include <bits/stdc++.h>
using namespace std;

int n;
long long s[200010],ans,a[100010],b[100010],c[200010];
int main()
{
 scanf("%d",&n);
 long long ji1=0,ji2=0;
 for(int i=1;i<=n;++i)
 {
  scanf("%lld%lld",&a[i],&b[i]);
  c[i]=a[i];
  c[i+n]=b[i];
  ji1+=a[i];
  ji2+=b[i];
 }
 ans=min(ji1,ji2);
 sort(c+1,c+2*n+1);
 for(int i=1;i<=n;++i)
 s[i]=s[i-1]+c[i];
 for(int i=1;i<=n;++i)
 {
  long long x=a[i],y=b[i];
  if(x>y)
  swap(x,y);
  if(lower_bound(c+1,c+2*n+1,x)-c<=n-2)
  {
   if(lower_bound(c+1,c+2*n+1,y)-c<=n-1)
   ans=min(ans,s[n]);
   else
   ans=min(ans,y+s[n-1]);
  }
  else
  ans=min(ans,x+y+s[n-2]);
 }
 printf("%lld\n",ans);
 return 0;
}