2018.3.28【 AtCoder beginner092-C 】解题报告（线性处理）-白红宇的个人博客

2018.3.28【 AtCoder beginner092-C 】解题报告（线性处理）

发布日期：2022-01-30 02:41:34 浏览次数：7 分类：技术文章

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

C - Traveling Plan

Time limit : 2sec / Memory limit : 256MB

Score : 300 points

Problem Statement

There are N sightseeing spots on the x-axis, numbered 1,2,…,N. Spot i is at the point with coordinate Ai. It costs |a−b| yen (the currency of Japan) to travel from a point with coordinate a to another point with coordinate b along the axis.

You planned a trip along the axis. In this plan, you first depart from the point with coordinate 0, then visit the N spots in the order they are numbered, and finally return to the point with coordinate 0.

However, something came up just before the trip, and you no longer have enough time to visit all the N spots, so you decided to choose some i and cancel the visit to Spot i. You will visit the remaining spots as planned in the order they are numbered. You will also depart from and return to the point with coordinate 0 at the beginning and the end, as planned.

For each i=1,2,…,N, find the total cost of travel during the trip when the visit to Spot i is canceled.

Constraints

2≤N≤105

−5000≤Ai≤5000 (1≤i≤N)

All input values are integers.

Input

Input is given from Standard Input in the following format:

NA1 A2 … AN

Output

Print N lines. In the i-th line, print the total cost of travel during the trip when the visit to Spot i is canceled.

Sample Input 1

Copy

33 5 -1

Sample Output 1

Copy

Spot 1, 2 and 3 are at the points with coordinates 3, 5 and −1, respectively. For each i, the course of the trip and the total cost of travel when the visit to Spot i is canceled, are as follows:

For i=1, the course of the trip is 0→5→−1→0 and the total cost of travel is 5+6+1=12 yen.

For i=2, the course of the trip is 0→3→−1→0 and the total cost of travel is 3+4+1=8 yen.

For i=3, the course of the trip is 0→3→5→0 and the total cost of travel is 3+2+5=10 yen.

Sample Input 2

Copy

51 1 1 2 0

Sample Output 2

Copy

Sample Input 3

Copy

6-679 -2409 -3258 3095 -3291 -4462

Sample Output 3

Copy

21630216301993289242163019288

【题目大意】

数轴上，按顺序从原点出发到x1,x2,x3......xn坐标位置，最后再返回原点。总路径为len。

依次跳过x1,x2,x3.....每个中间点，跳过后的路径为len1,len2,len3......依次输出

【解题思路】

头和尾部补0，先读入，计算总路径以后离线处理。

如果该结点恰在前后节点中间，则总路径不变。

如果该结点再前后结点的同侧（包括首位的0结点），那么总路径=原总路径-2min（前后节点与该结点的差值）

【解题代码】

#include 
   
    #include
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #define For(i,n) for(int i=0;i
            
             a[i-1]) sum+=a[i]-a[i-1]; else sum+=a[i-1]-a[i]; } a[n+1]=0; sum+=abs(a[n+1]-a[n]);// printf("sum=%d\n",sum); for(int i=1;i<=n;i++) { if(a[i]>=a[i-1]&&a[i]<=a[i+1]||a[i]<=a[i-1]&&a[i]>=a[i+1]) printf("%d\n",sum); else { int l1=abs(a[i]-a[i-1]); int l2=abs(a[i+1]-a[i]); int minn=min(l1,l2); printf("%d\n",sum-2*minn); } }}

【收获与反思】

水过。

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

上一篇：2018.4.10【 POJ - 1995 】解题报告（快速幂学习，模板题）

下一篇：2018.4.10【 HDU - 2035 】解题报告（快速幂，水题）

发表评论

关于作者

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

-- 愿君每日到此一游！

C - Traveling Plan

Problem Statement

Constraints

Input

Output

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

发表评论

最新留言

关于作者

推荐文章