贪心，构造学习笔记
贪心构造不会
黄题绿题懵逼
横批：依托答辩
\(\text{CF1764C}\)
题目描述
有一些点，每一个点有一个点权 \(a_i\) 。你可以在任意点之间连边，最终的图需要满足不存在 \(a,b,c\) 满足 \(a_a \leqslant a_b \leqslant a_c\) 并且 \(ab,bc\) 之间有连边。
思路点拨
我们连出来的图一定可以被划分为一个二分图。不然就会存在奇环，而不论你怎么构造，奇环上就是会有一条路径不满足条件。
所以我们可以枚举一个值域的划分，假设枚举 \(w\) 这个值，那么我们让 \(a_i \leqslant w\) 的点进入左部，反之进入右部。我们最终可以让左部的每一个点都连向右部的每一个点，这样就可以满足条件。因为全部的二分图中，想要连边最多，全部的情况我们都考虑到了。
但是还存在一种极端的情况，就是划分不出来一个二分图使得左部和右部都非空，也就是说，全部的值都相等。这个时候，我们发扬人类智慧，让最终的图不存在长度为 \(2\) 的路径就可以了，所以答案就是 \(\lfloor\dfrac{n}{2} \rfloor\) 。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+10;
int T,n,a[MAXN];
signed main(){
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<n;i++)
if(a[i]!=a[i+1])
ans=max(ans,i*(n-i));
cout<<max(ans,n/2)<<endl;
}
return 0;
}
\(\text{Luogu3918}\)
题目描述
有一个飞行表演持续 \(n\) 个单位时间，每一个单位时间都可以表演一种特技，共有 \(k\) 种特技。表演具有价值之说，我们给定了一个长度为 \(k\) 的序列 \(c\) ，一次表演的价值就是距离上次表演这个特技的时间乘上 \(c_i\) 。我们希望让表演的总价值最大。
思路点拨
我们考虑对于一种特技假设他出现位置的序列为 \(pos_1,pos_2,...,pos_m\) ，那么他的价值就是：\(\sum_{i=1}^{m-1}(pos_{i+1}-pos_{i})c_j\)，那么就是 \((pos_m-pos_1)c_j\) 。说人话就是这个特技最后出现的时间减去这个特技第一次出现的时间乘上 \(c_j\) ，我们进而贪心的，每一个特技要么不出现，要么出现两次。
我们猜一个结论，我们按照 \(c\) 从大到小排序，每一次找到最长的区间之后，让这个区间的左右端点都表演目前还未表演的， \(c\) 最大的那个特技。比较抽象，代码就是：
for(int i=1;i<=k;i++) cin>>a[i];
sort(a+1,a+k+1,cmp);
int ans=0;
for(int l=1,r=n,pos=1;l<r;l++,r--)
ans+=(r-l)*a[pos++];
但是为什么是对的呢？我们考虑使用交换法来证明。假设存在两个下表 \(i,j\) ，\(i,j\) 第一次出现的位置和最后一次出现的位置分别是： \(l_i,l_j,r_i,r_j\) 。并且 \(c_i>c_j\) ， \(l_i<l_j<r_j<r_i\) 。那么如果存在：
因为 \((l_i-l_j)\) 是负数，而 \(c_i>c_j\) ，所以这种情况是不可能的，按照上述方法贪心有最优解。