题目描述

有很多节火车厢被分散在一条轨道上的若干个位置

第i节车厢在position[i]的位置，长度为length[i]，也就意味着第i节车厢占据了{ position[i], position[i]+length[i] }这段区间

移动一节车厢一个单位长度需要消耗一个单位的能量，现在问你最少需要消耗多少能量能够将所有的车厢合并到一起，即任意两节车厢之间都没有间隙

输入

第一行先输入一个整数n (2 <=n <=50)

第二行输入n个整数 position[i] (1 <= position[i] <=10^9)

第三行输入n个整数 length[i] (1 <= length[i] <= 10^9)

输出

输出一个整数,表示需要消耗的最少能量

样例输入

【样例输入1】

4

1 3 10 20

2 2 5 3

【样例输入2】

3

100 50 1

10 2 1

【样例输入3】

5

4 10 100 13 80

5 3 42 40 9

样例输出

【样例输出1】

15

【样例输出2】

96

【样例输出3】

66

题意:合并区间,使其所有都合并成一个区间.

因为数据范围比较小,所以直接暴力.

题解:先按左端排序,枚举每一个车厢,以其为中心,两边的车厢向他靠拢.

#include 
    
     using namespace std;const int N=100;typedef long long ll;struct p{    ll l,r;}a[N];typedef long long ll;bool comp(p a,p b){    return a.l
     
      >n;     for(int i=1;i<=n;i++) cin>>a[i].l;     for(int i=1;i<=n;i++){        cin>>a[i].r;        a[i].r+=a[i].l;     }     sort(a+1,a+1+n,comp);     int end;     ll ans=0;     ll minn=1e18;     for(int i=1;i<=n;i++){        end=a[i].l;        ans=0;        for(int j=i-1;j>=1;j--){            ans+=end-a[j].r;            end-=a[j].r-a[j].l;          }         end=a[i].r;         for(int j=i+1;j<=n;j++){            ans+=a[j].l-end;            end+=a[j].r-a[j].l;         }         if(ans