VIJOS 1780 开车旅行-白红宇的个人博客

VIJOS 1780 开车旅行

发布日期：2022-02-05 18:27:32 浏览次数：15 分类：技术文章

本文共 2080 字，大约阅读时间需要 6 分钟。

描述

小A和小B决定利用假期外出旅行，他们将想去的城市从1到N编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i 的海拔高度为Hi，城市i 和城市j 之间的距离d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i,j] = |Hi - Hj|。

旅行过程中，小A和小B轮流开车，第一天小A开车，之后每天轮换一次。他们计划选择一个城市S作为起点，一直向东行驶，并且最多行驶X公里就结束旅行。小A和小B的驾驶风格不同，小B总是沿着前进方向选择一个最近的城市作为目的地，而小A总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出X公里，他们就会结束旅行。

在启程之前，小A想知道两个问题：

1．对于一个给定的X=X0，从哪一个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值最小（如果小B的行驶路程为0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值都最小，则输出海拔最高的那个城市。

2. 对任意给定的X=Xi 和出发城市Si，小A开车行驶的路程总数以及小B行驶的路程总数。

格式

输入格式

第一行包含一个整数N，表示城市的数目。

第二行有N个整数，每两个整数之间用一个空格隔开，依次表示城市1到城市N的海拔高度，即H1，H2，……，Hn，且每个Hi 都是不同的。

第三行包含一个整数X0。

第四行为一个整数M，表示给定M组Si和Xi。

接下来的M行，每行包含2个整数Si 和Xi，表示从城市Si 出发，最多行驶Xi 公里。

输出格式

输出共M+1行。

第一行包含一个整数S0，表示对于给定的X0，从编号为S0的城市出发，小A开车行驶

的路程总数与小B行驶的路程总数的比值最小。

接下来的M行，每行包含2个整数，之间用一个空格隔开，依次表示在给定的Si 和Xi 下小A行驶的里程总数和小B行驶的里程总数。

样例1

样例输入

4 2 3 1 4 3 4 1 3 2 3 3 3 4 3

样例输出

1 1 1 2 0 0 0 0 0

样例2

样例输入

10 4 5 6 1 2 3 7 8 9 10 7 10 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7

样例输出

2 3 2 2 4 2 1 2 4 5 1 5 1 2 1 2 0 0 0 0 0

限制

每个测试点1s

提示

对于30%的数据，有1≤N≤20，1≤M≤20；

对于40%的数据，有1≤N≤100，1≤M≤100；

对于50%的数据，有1≤N≤100，1≤M≤1,000；

对于70%的数据，有1≤N≤1,000，1≤M≤10,000；

对于100%的数据，有1≤N≤100,000，1≤M≤10,000，-1,000,000,000≤Hi≤1,000,000,000，0≤X0≤1,000,000,000，1≤Si≤N，0≤Xi≤1,000,000,000，数据保证Hi 互不相同。

来源

Noip2012提高组复赛Day1T3

这个题想到了模拟。。。。

T3居然是模拟。。。

其实70分感觉非常简单

首先预处理出每个点向后的最短次短的目的地和距离

然后模拟一下啦

。。。。。。。。

另外比值那个东西要开到19亿才能70

一开始拙计开9亿999 只有65 还不错。。。

不用long long也可以70 = =

贴代码吧

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int lim=1011;const int inf=1999999999;struct side{int x,y,h,w;}s[lim*lim];struct self{int first,nxt,fw,nw;}g[lim];int m,casenum,n,a,b,c,h[lim];int x,y,l,r,ans,ansh;double bizhi=0;inline int Abs(int i){return i<0?-i:i;}int cmp(side a1,side a2){return a1.w==a2.w?a1.h
       
        
         s[a].w) }}void work(int from,int dis,int now){ //cout<<"work("<
         
          <<","<
          
           <<","<
           
            <<")"<
            
             ansh&&bizhi>inf-1) { ansh=h[a]; ans=a; } if(r!=0&&(double)l/r

AC做法

如果有时间的话再研究下

NOIP RP++

转载地址：https://blog.csdn.net/li412302070/article/details/14160981 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：VIJOS 1776 关押罪犯

下一篇：VIJOS 1362 树网的核

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

描述

格式

输入格式

输出格式

样例1

样例输入

样例输出

样例2

样例输入

样例输出

限制

提示

来源

发表评论

最新留言

关于作者

推荐文章