题解 P4653 【[CEOI2017]Sure Bet】
既然没有人写题解，那我就首当其冲吧
这道题方法其实很多
先说明一点，每次可以从 A类 获得 a 的权值，从 B类 获得 b，最小的情况是 min(a,b)，题目要我们求的就是最大的 min(a,b)
第一眼看上去就像动态规划，但是具体怎么规划我不知道
但是有一点确定，动态规划的朋友们，数据给你的权值要乘以 10^4 不然无法规划，数组也要开到原来的 10^4 倍
好了废话到此为止，重头戏现在开始
法一：三分法
这其实是这道题的正解
三分法，名字十分形象，跟二分法很类似，只不过它是每次三等分，有些情况会比二分快
比如这道题，其实二分根本做不了，只能用三分
为什么呢？大家都知道，二分的前提是数据呈单调上升，这样我们才能把一条图像分成大与小两部分
类似于这种图像，是二分所适用的，因为纵着切一刀可以分成大小一眼可辨的大与小两瓣
但是很显然，因为受“每拿一个灯泡就要耗费一权值”的限制，函数不呈单调上升，那是什么样呢？
是类似的二次函数，满足规律“先上升再下降”（二次函数性质易证）
而我们要求的答案自然在最高处的“屈服点”
而我们用三分法对答案进行试探，每次三分必然产生“左，中，右”三段，而再进一步分析左中右的走势再判断屈服点在那一段
具体说，我们找到了两个点，a 与 b，把这一段分成了三段
-
a<=b时，答案则锁定在中与右段，则继续三分 a~R 段
-
a>b 时，答案则锁定在左与中段，则三分 L~b 段
具体代码就不展示了，因为我不是用三分过的 qwq
法二：贪心（枚举）
我是用这个神奇算法过的，没有三分那么高大上
由于每一次都要花费一权值，那么高权值的灯泡不拿白不拿，那就全拿上了！
然而并不能很粗暴地全拿光，因为有可能好灯泡不是在 A类 与 B类 均匀分布的
所以更好的方法，是从 A类 拿一个贼大的，然后再从 B类 拿一堆尽量与 A 所获得的价值屏平衡
B 比 A 获得的多的时候，A 就不能坐以待毙了，要开始拿灯泡了
其实就是不断调整 A 与 B 获得的价值，使他们尽量平均
奉上代码（终于啊）
/*
n 个 A组 灯泡
n 个 B组 灯泡
你在其中任意选灯泡（每个灯泡有它的价值）
每选一个要用一块钱
选完之后任意点亮已选的 A 或 B 灯泡
你会得到相应的价值
求最大的最小收益
(A 类得 a ，B 类得 b，求最大的min(a,b))
*/
#include<bits/stdc++.h>
using namespace std;
int n;
double A[100001],B[100001],ans;
bool visit[100001][2];
bool cmp(double a,double b)
{return a>b;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) cin>>A[i]>>B[i];
sort(A+1,A+n+1,cmp);
sort(B+1,B+n+1,cmp);
double a=0.0,b=0.0;
for(double i=1,j=1;i<=n && j<=n;)
{
int x=i,y=j;
a+=A[x]*double(!visit[x][0]);
b+=B[y]*double(!visit[y][1]);
visit[x][0]=visit[y][1]=1;
ans=max(ans,min(a-i-j,b-i-j));
if(a>=b) j++;
if(a<=b) i++;
}
printf("%.4lf",ans);
return 0;
}话说这道题又不难，怎么没人写题解呢QAQ