【uva 11093】Just Finish it up(算法效率--贪心)
2024-10-21 13:04:14
题意:环形跑道上有N个加油站,编号为1~N。第 i 个加油站可以加油Ai加仑,从加油站 i 开到下一站需要Bi加仑汽油。问可作为起点走完一圈后回到起点的最小加油站编号。
解法:我们把每个加油站的Ai,Bi合并,把Ai-Bi看成N个点的权Ci,表示经过 i 的剩余油量。可知可通过第 i 个加油站就是sum{}+Ci>=0,sum{}表示从起点开到 i 之前剩余的油量,sum{}>=0。因此,若sum{}+Ci<0,那么从这时枚举的起点到 i 之间的所有点都不能作为起点,因为这时的sum{}已经是以他们为起点所能达到的最大值了,不可能有更多的油量剩余,一定不能通过点 i。便枚举 i+1 为起点,继续判断。
P.S.由于是环,判断走完一圈也有点麻烦,大家要小心。我觉得我打的虽然比较短,但也不是很优美。= =
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<algorithm>
5 #include<iostream>
6 #include<queue>
7 using namespace std;
8 const int N=100010;
9
10 int n;
11 int a[N],b[N];
12 int mmax(int x,int y) {return x>y?x:y;}
13 int check(int x)
14 {
15 int h=0,t=x;
16 bool tf=true;
17 while(1)
18 {
19 if (t==x&&!tf) return -1;
20 h+=a[t]-b[t];
21 if (h<0) return t;
22 tf=false;
23 t=(t+1)%n;
24 }
25 }
26 int main()
27 {
28 int T;
29 scanf("%d",&T);
30 for (int kase=1;kase<=T;kase++)
31 {
32 scanf("%d",&n);
33 for (int i=0;i<n;i++) scanf("%d",&a[i]);
34 for (int i=0;i<n;i++) scanf("%d",&b[i]);
35 int ans=n,x=0,tmp,mx=-1;
36 while (1)
37 {
38 if (x<=mx) break;
39 tmp=check(x),mx=mmax(mx,x);
40 if (tmp==-1) {ans=x;break;}
41 else x=tmp+1;
42 }
43 if (ans!=n) printf("Case %d: Possible from station %d\n",kase,ans+1);
44 else printf("Case %d: Not possible\n",kase);
45 }
46 return 0;
47 }
最新文章
- Lind.DDD.ConfigConstants统一管理系统配置
- KALI LINUX WEB 渗透测试视频教程—第16课 BEEF基本使用
- PAAS平台的web应用性能测试与分析
- Cisco ASA 高级配置
- 一个DataTable赋值给另一个DataTable的常用方法
- windows下 berkerly db的安装配置(修正了关键步骤)
- java中hashcode和equals的区别和联系
- 【微机】验证负数以补码存储程序 C语言
- HDU 5916 Harmonic Value Description 【构造】(2016中国大学生程序设计竞赛(长春))
- ReactiveCocoa Tutorial
- externkeyword放到函数体内而导致的linkage问题
- IOS SWIFT 简单操作文件
- hdu_3336: Count the string(KMP dp)
- Python+Selenium安装及环境配置
- win8如何共享文件夹
- 生成表结构数据库文档sql语句
- python参数
- 欧拉函数,打表求欧拉函数poj3090
- code first 创建数据库,add-migration update-database
- 在浏览器输入URL后发生了什么?
热门文章
- LeetCode237 删除链表中的节点
- oracle 11g 安装与卸载
- 【TNS】listener.ora模板;tnsnames.ora模板
- 【Linux】postfix大坑笔记
- 【Oracle】查询锁的相关SQL
- 入门训练 - 蓝桥杯(Python实现)
- 基于FPGA的光口通信开发案例|基于Kintex-7 FPGA SFP+光口的10G UDP网络通信开发案例
- JAVA中@Override的含义
- Py数据类型—整形与字符串
- [阿里DIEN] 深度兴趣进化网络源码分析 之 Keras版本