洛谷$P$2123 皇后游戏 贪心
正解:贪心
解题报告:
传送门!
心血来潮打算把$luogu$提高历练地及其之前的所有专题都打通关,,,$so$可能会写一些比较水的题目的题解$QAQ$
这种题,显然就套路地考虑交换相邻两个人的次序的影响嘛
瞎写下式子,大概是长这样儿(就只考虑更大的那个$C$了昂$QwQ$)
$\left\{\begin{matrix}
max(max(C,A+a_{x})+b_{x},A+a_{x}+a_{y})+b_{y}\\
max(max(C,A+a_{y})+b_{y},A+a_{y}+a_{x})+b_{x}
\end{matrix}\right.$
注意,其实这个是可以化简的,就把外面的给放进去,变成这样儿
$\left\{\begin{matrix}
max(C+b_{x}+b_{y},A+a_{x}+b_{x}+b_{y},A+a_{x}+a_{y}+b_{y})\\
max(C+b_{y}+b_{x},A+a_{y}+b_{y}+b_{x},A+a_{y}+a_{x}+b_{x})
\end{matrix}\right.$
如果现在是要$x$在$y$的前面,则有
$max(C+b_{x}+b_{y},A+a_{x}+b_{x}+b_{y},A+a_{x}+a_{y}+b_{y})\leq max(C
+b_{y}+b_{x},A+a_{y}+b_{y}+b_{x},A+a_{y}+a_{x}+b_{x})$
再设一个$sum_{a}$表示$a_{x}+a_{y}$,$sum_{b}$表示$b_{x}+b_{y}$
原来那个式子就差不多长成这样儿了:
$max(C+sum_{b},A+a_{x}+sum_{b},A+sum_{a}+b_{y})\leq max(C+sum_{b},A
+a_{y}+sum_{b},A+sum_{a}+b_{x})$
显然有$C\leq A+a_{x}$是可以被直接消掉的(过于显然不想证了,,,如果有问题在下面
留言我再随便口胡下证明趴$QAQ$),所以式子又可以变成
$max(A+a_{x}+sum_{b},A+sum_{a}+b_{y})\leq max(A+a_{y}+sum_{b},A+sum_
{a}+b_{x})$
于是显然$A$就可以被消掉了,就变成了
$max(a_{x}+sum_{b},sum_{a}+b_{y})\leq max(a_{y}+sum_{b},sum_{a}+b_{x})$
再又展开得
$max(a_{x}+b_{x}+b_{y},a_{x}+a_{y}+b_{y})\leq max(a_{y}+b_{x}+b_
{y},a_{x}+a_{y}+b_{x})$
把一些东西又提出来得
$max(b_{x},a_{y})+a_{x}+b_{y}\leq max(b_{y},a_{x})+a_{y}+b_{x}$
考虑大力分类讨论$bushi$(其实在这儿的时候大力分类讨论就已经能做出来辣,,,?只是
贼麻烦$QwQ$
考虑继续移项
$max(b_{x},a_{y})-a_{y}-b_{x}\leq max(b_{y},a_{x})-b_{y}-a_{x}$
$-min(b_{x},a_{y})\leq -min(b_{y},a_{x})$
于是终于得出了最后的结论
$min(b_{x},a_{y})\geq min(b_{y},a_{x})$
然而你以为到这儿就完了嘛$QAQ$
$naive$,紫题还是麻油那么好评的鸭$QwQ$
我先放个数据:
```
3
7 3
1 1
1 6
3
1 1
1 6
7 3
```
显然我只是调换了一下大臣们的站位而已的$QwQ$
但是如果直接按那样子排序然后直接算出来$C$,输出会不一样,,,
为什么呢,仔细思考一下,发现是因为满足$min(b_{x},a_{y})\geq min(b_{y},a_{x}
)$的排序方式其实有很多(比如上面两个就都是的$QwQ$
然后在实际计算的过程中,前一个会是:$C_{1}=10\ C_{2}=11\ C_{3}=17$
后一个则是:$C_{1}=2\ C_{2}=8\ C_{3}=12$
简单来说,这个比较不具有传递性,就是这个结论只能适用于相邻两个数之间的比较,当
拓展到多个数时就会$GG$了(具体证明看这个趴,,,太神了没看太懂$TT$
当然这个结论在$min(b_{x},a_{y})\neq min(b_{y},a_{x})$的情况下还是$AC$的,
只是要考虑当$min(b_{x},a_{y})=min(b_{y},a_{x})$的时候要怎么比较
不难想到就,直接对$a$从小到大排就好鸭$QwQ$
然后就做完辣!
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
#define gc getchar()
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i) const int N=+;
struct node{int x,y;}nod[N]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il bool cmp(node gd,node gs){return min(gd.x,gs.y)!=min(gd.y,gs.x)?min(gd.x,gs.y)<min(gd.y,gs.x):gd.x<gs.x;} main()
{
int T=read();
while(T--)
{
ri n=read();rp(i,,n)nod[i]=(node){read(),read()};sort(nod+,nod++n,cmp);
ri as=nod[].x+nod[].y,sum=nod[].x;
rp(i,,n)
{
sum+=nod[i].x;as=max(as,sum)+nod[i].y;
}
printf("%lld\n",as);
}
}
最新文章
- Wave - 花たん 音乐
- 一些Unity基础操作的性能测试
- 个推,手机推送API的使用
- hdu1754 I hate it线段树模板 区间最值查询
- spring mvc 解决后台传递值乱码问题
- open Session In View和过滤器配置
- git的那点事---
- [tools]tcp/udp连通性测试
- Progress 自定义(一)-shape
- 第11条:谨慎地覆盖clone
- (转)Smarty Foreach 使用说明
- Codeforces 486D D. Valid Sets
- C语言之固定格式输出当前时间
- stl中auto_ptr,unique_ptr,shared_ptr,weak_ptr四种智能指针使用总结
- python_如何读写csv数据
- Linux 安装配置 FTP 服务 (vsftpd)
- DUILIB UI创建过程
- docker 2 docker介绍
- PLSQL 使用技巧汇总贴(一个坑)
- hadoop 学习笔记2
热门文章
- oracle函数 CHR(n1)
- TensorFlow 池化层
- @bzoj - 4378@ [POI2015] Logistyka
- 2、asp.net core 部署到服务器之后外网访问不了
- 使用sqlyog链接多个主机的数据库
- 2012.2.1datagridview用法小结
- localStorage、sessionStorage、cookie的区别
- jq添加插入删除元素
- POJ 2406 Power Strings next数组循环节应用、
- java super关键字和调用父类构造方法