牛杂技团

  题目大意:一群牛想逃跑,他们想通过搭牛梯来通过,现在定义risk(注意可是负的)为当前牛上面的牛的总重量-当前牛的strength,问应该怎么排列才能使risk最小?

  说实话这道题我一开始给书上的二分法给弄懵了,后来看了一下题解发现根本不是这么一回事,其实就是个简单的贪心法而已。

  这题怎么贪心呢?就是按w+s从小到大排序就好了,证明一下:

  1.先证明如果不满足w+s的序列性,无论谁在谁的上面,都会违反题设:(设A在B的上面)

    如果 A.s+A.w<B.s+B.w

    则如果B.s<m+A.w

    则如果B在A的上面A.s<B.s+B.w-A.w=B.w+m

    得证

  2.再证明一下如果采用排序的确能让risk的最大值最小。

    如果 A.s+A.w<B.s+B.w

    ①A在B的上面

    riskA1=m-A.s  riskB1=m+A.w-B.s

    ②B在A的上面

    riskB2=m-B.s  riskA2=m+B.w-A.s

    所以riskA2>riskA1

      另外riskB1-riskA2=A.w+A.s-B.w-B.s<0  所以riskA2>riskB1>riskB2

    则违反后risk会产生一个比三个risk更大的数,不符合题意

    参考http://poj.org/showmessage?message_id=341726

 #include <iostream>
#include <algorithm>
#include <functional> using namespace std;
typedef long long LL_INT; typedef struct _cows
{
LL_INT strength;
LL_INT weight;
bool operator<(const _cows &x) const
{
return strength + weight > x.weight + x.strength;
}
}Cows; static Cows cows_set[];
void Search(const int, LL_INT);
bool judge(const LL_INT, const int,const LL_INT); int main(void)
{
int sum_cows;
LL_INT sum_w; while (~scanf("%d", &sum_cows))
{
sum_w = ;
for (int i = ; i < sum_cows; i++)
{
scanf("%lld%lld", &cows_set[i].weight, &cows_set[i].strength);
sum_w += cows_set[i].weight;
}
sort(cows_set, cows_set + sum_cows);
Search(sum_cows,sum_w);
}
return ;
} void Search(const int sum_cows, LL_INT sum_w)
{
LL_INT ans = -; for (int i = ; i < sum_cows; i++)
{
sum_w -= cows_set[i].weight;
ans = max(ans, sum_w - cows_set[i].strength);
}
cout << ans << endl;
}

其实这题的思想和Protecting Flowers那题有点像,都是只看两个元素之间的两个量之间的练联系,而不只是单单的一个量

最新文章

  1. 彻底解决m2eclipse之Unable to update index for central
  2. 【Java】模板方法模式
  3. rsync同步完整配置
  4. C陷阱与缺陷 2
  5. JedisPool连接池实现难点
  6. jackson使用示例
  7. 修改EditText的光标位置
  8. POJ 2075 Tangled in Cables (c++/java)
  9. 前端优化:BigRender
  10. 关于函数strtok和strtok_r的使用要点和实现原理(二)
  11. Unity 3.5
  12. sqlserver中分区函数 partition by与 group by 区别 删除关键字段重复列
  13. Java 批量导入大量数据
  14. BZOJ3718[PA2014]Parking——树状数组
  15. zabbix监控Windows-server
  16. Unittest + python
  17. 使用 Python 把多个 MP4 合成一个视频(转)
  18. burpsuite的使用(三)
  19. finger-guessing game:3增加猜拳次数及猜拳按钮显示
  20. PAT L2-005 集合相似度(模拟集合set)

热门文章

  1. linux socket
  2. 密码学初级教程(一)基本概念及DES加密算法
  3. 1455.Solitaire(bfs状态混摇)
  4. 使用 Github Pages 发布你的项目文档
  5. UNITY3d在移动设备上的一些优化实战(一)-概述
  6. Windows系统使用putty远程连接DigitalOcean创建的Linux系统(CentOS6.7为例)
  7. git 教程(11)--从远程库克隆
  8. Sound Generator 原理
  9. C语言文件操作
  10. Android 本地加载网页与显示网络图片