ACM 模拟 Just Finish it up

╰+攻爆jí腚メ 2022-06-12 14:56 164阅读 0赞

滴，集训第八天打卡。

今天还是第八章训练，看着书上的分析做了一下午，感觉人生得到了升华...

**UVA 11093 Just Finish it up**

**![20170725113532823][]**

**![20170725113540221][]**

**题目大意：环形跑道上有N个加油站，编号为1~N.第i个加油站可以加pi升油，从加油站i开到下一站需要qi升油。你可以选择一个加油站作为起点，初始油箱为空，但可以立即加油。任务是选择一个起点，使得可以走完一圈。**

**思路：枚举模拟，考虑一号加油站，直接模拟判断它是否为解。如果是，直接输出，如果不是，说明在模拟过程中遇到了某个加油站p，在从它开到加油站p+1时油没了。于是下一次模拟直接从p+1开始即可。**

#include <stdio.h>
    int main()
    {
    	int t,n,i,j,a[100005],b[100005],o=1,s,p,k,kk;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		for(i=0;i<n;i++)
    		scanf("%d",&a[i]);
    		for(i=0;i<n;i++)
    		scanf("%d",&b[i]);
    		printf("Case %d: ",o++);
    		s=0;p=0;k=0;kk=0;
    		while(p<n)
    		{
    			k=0;s=0;
    			for(i=p;i<n+p;i++)
    			{
    				j=i;
    				if(j>=n)//环形跑道，要绕一圈
    				j-=n;
    				s+=a[j];
    				s-=b[j];
    				if(s<0)
    				{
    					p=j+1;//起点变更
    					k=1;
    					break;
    				}
    			}
    			if(i!=j&&k==1)break;
    			if(k==0)
    			{
    				kk=1;
    				printf("Possible from station %d\n",p+1);
    				break;
    			}
    		}
    		if(kk==0)
    		printf("Not possible\n");
    	}
    }

[20170725113532823]: /images/20220612/f9242f2f49dd46d997a3b1214a79bdc6.png
[20170725113540221]: /images/20220612/a03da8eb1e604190a25d091827bf3afc.png

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关 Sum It Up

Sum It Up Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

谁借莪１个温暖的怀抱￠/ 2024年02月18日 23:13/ 0 赞/ 50 阅读

相关 Just do it，一起来玩篮球吧

沉寂了近一年之后，三维可视化工具箱WxGL终于又有版本更新了：从0.6.4升级到0.7.0（现在安装的话也可能是0.7.2），并且承诺自0.7.0版本开始向后兼容。在正式发布d

水深无声/ 2022年10月12日 01:18/ 0 赞/ 203 阅读

相关 Just Do It

最近事情少了一些每天拿出一点时间来读书，最近看了两本书给大家分享一下，里面有很多米老师提到的观点。《你远比想象中强大》这

忘是亡心i/ 2022年08月17日 15:16/ 0 赞/ 95 阅读

相关广州电商行---Just do IT

我的日子一页一页的翻着,从广州回来,转眼,由夏天一下翻到了冬天,衣服由简到繁,鞋子由凉变暖.荏苒的时光悄悄流逝,迈入了新的一年,在广州的日子,仿佛如昨天一样历

╰+攻爆jí腚メ/ 2022年07月13日 08:15/ 0 赞/ 150 阅读

相关 Relax! It’s just a game HDU - 2922

Relax! It’s just a game HDU - 2922 -------------------- Problem You: What’s the s

旧城等待，/ 2022年06月14日 10:40/ 0 赞/ 138 阅读

相关 ACM 模拟 Just Finish it up

滴，集训第八天打卡。今天还是第八章训练，看着书上的分析做了一下午，感觉人生得到了升华... UVA 11093 Just Finish it up ![20

╰+攻爆jí腚メ/ 2022年06月12日 14:56/ 0 赞/ 165 阅读

相关 hdu--6129--Just do it

Just do it Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 524288/524288 K (J

落日映苍穹つ/ 2022年06月10日 13:36/ 0 赞/ 157 阅读

相关 Sum It Up

Sum It Up Problem Description Given a specified total t and a list of n integers, f

阳光穿透心脏的1/2处/ 2022年05月16日 11:21/ 0 赞/ 126 阅读

相关 HDU-1258 Sum It Up （DFS）

题意：输入一个m，和n个数，输出所有数据组合相加和为m的组合，输出的数列不重复； emmmm....一开始是想dfs全找出来存起来然后去重，然后发现自己数据结构也很菜，实现不

约定不等于承诺〃/ 2021年10月19日 11:22/ 0 赞/ 203 阅读

相关 B. Light It Up （前缀和、模拟）

[题目][Link 1] 预先做好一个所有偶数与前一个数差值和3以后奇数a\[i\]和前一个数差值的前缀和b\[i\]（代表插入数后的情况），然后遍历插入到所有数后面的情

╰半橙微兮°/ 2021年07月16日 11:25/ 0 赞/ 341 阅读