• 题目来源:3177
  • 题目分析:一只蝎子要搬动一堆装备到一个容量为V的洞里面,每个装备有两个属性,一个是固有体积A,放置之后洞的剩余空间就会减少A,一个是移动体积B,只有当体积B小于等于当前洞的剩余体积的时候才能放进去。判断能不能把装备都放进去。
    0< T<= 10, 0< V<10000, 0< N<1000, 0 < Ai< V, Ai <= Bi < 1000.
  • 我的思路: 首先,采用贪心策略
    一开始我是按照移动体积B从大到小排序的,这是错的,因为没有考虑到每次放入装备之后的空间减少的问题。之后加入了空间大小的判断,还是按照B排序,同时剔除移动体积B大于洞的大小V(当时我没想到剩余空间,以为就是个门槛而已)的判断,结果是WA。

  • 拿样例来说:
    20 3
    10 20
    3 10
    1 7
    即洞的体积V是20,有3件装备。
    分别是:

属性 固有体积(A) 移动体积(B)
第一件 10 (A1) 20 (B1)
第二件 3 (A2) 10(B2)
第三件 1(A3) 7(B3)

如果按照这个顺序放的话,先放第一个,B1<=剩余空间(此时是20),放进去之后洞的体积减少A1,之后放第二个B2<=剩余空间(此时是10),放入之后洞的体积减少A2,最后放第三个,B3<=剩余空间(此时是7),这样就都放进去了。
但是假如换个顺序,先放入A2,之后是A3,A1,就放不进去。
- 扩展到第i个装备和第j个装备:

属性 固有体积(A) 移动体积(B)
第i个 ai bi
第i个 aj bj

先放入第i个,需要至少(ai+bj)的空间,那么反过来就需要至少(aj+bi)的空间,那么这种情况下,当然是选择更小的那个,即min(ai+bj,aj+bi);
所以按照应该按照ai+bj从大往小排序

ai+bj< aj+bi, 按照这个式子不好写,同时根据Ai <= Bi < 1000可知移动体积不小于固有体积,所以移项,同一个装备的放一起, 就变成了
bj-bi< aj-ai 之后排序,再判断,输出结果。

  • 完整代码:
#include<stdio.h>
typedef struct
{
int need; //固有体积
int move; //移动体积
}equip;
int main(void)
{
int T; //测试数目
scanf("%d", &T);
int v, n, i, j, flag; //洞的体积v,装备数目n,
equip a[1001], temp;
while (T-- > 0)
{
flag = 1;
scanf("%d%d", &v, &n);
for (i = 0; i < n; i++)
scanf("%d%d",&a[i].need,&a[i].move);
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - 1 - i; j++)
{
if ((a[j].move-a[j].need) < (a[j + 1].move-a[j+1].need)) //按照bj-bi< aj-ai排序
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
for (i = 0; i < n; i++)
{
if (a[i].move > v) //是否超过剩余体积
{
flag = 0;
break;
}
else
{
v -= a[i].need;
}
}
if (flag)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}

最新文章

  1. 运行带cocoa pods 的项目,遇到的问题是找不到文件,解决办法
  2. 【代码】verilog之:按键消抖
  3. Python学习笔记(2):数据库访问
  4. ADO.NET笔记——读取二进制大对象(BLOB)
  5. Mac Yosemite OS10.10 Apache 虚拟主机设置
  6. 性能优化之NSDateFormatter
  7. C#控件系列--文本类控件
  8. oracle 在操作blob该字段是否会产生很多redo
  9. python基础操作_集合_三元运算
  10. awk 详解+实例
  11. JQ-bootstrap我的开源前端框架
  12. html: 仿制soundmanager2右上角面板
  13. C#进阶系列——AOP
  14. PHP使用Redis实现消息队列
  15. JavaSE笔记
  16. Android学习笔记四:activity的四种启动模式
  17. 009-jdk1.8版本新特性一-展方法,Lambda表达式,函数式接口、方法引用构造引用
  18. Centos7下CPU内存等资源监控
  19. 编译Qt-mingw使用的opencv
  20. Coursera SDN M1.2.1 SDN History: Programmable Networks 1

热门文章

  1. nexus 私服相关的配置
  2. https的设计原理
  3. WPF 正確理解ContentPresenter
  4. Spring boot-(2) Spring Boot使用
  5. machine learning 线性回归实战
  6. Oracle同义词、索引、分区
  7. dreamweaver,access2010,数学
  8. Spring课程 Spring入门篇 3-4 Spring bean装配(上)之自动装配
  9. BZOJ4260: Codechef REBXOR (01Tire树)
  10. The sixteenth day