C - Candles

标签：cout int Candles pos abs res

题目链接：

C - Candles (atcoder.jp)

题目大意：

给你n个蜡烛的坐标，你想点燃其中k个蜡烛，一开始你在坐标0，每次向左或者向右可以移动一格，问点燃k个蜡烛至少需要移动多少步。

分析：

最优的移动的路线可以看作是一个‘U’型再加上一个线段。

以第一个样例为例：

 

 

 如图所示：

 

 

 蓝色部分是‘U’型，红色部分是线段。此时，该路径的长度是10 * 2 + 20 = 40.

因此，我们可以从第一个点开始遍历，该点既可以作为路径线段部分，也可以作为路径‘U’型的部分，如图所示：

 

 

 

 

 

 因此我们可以将所有的点分成两部分，小于等于0的作为一部分，大于0的作为一部分，a[pos]作为最后一个小于等于0的点。从第一个点开始遍历，直到a[pos]点。设该点到a[]点有m个点，则大于0的部分有k-m个点。然后再将两种路径比对一下大小即可。再处理一下特殊情况。

AC代码：

#include <iostream>
#include <algorithm>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
using namespace std;
const int N = 100010, inf = 1e10;
int n, a[N], k, pos;
signed main(){
    ios;
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> a[i];
    pos = n;
    for(int i=1;i<n;i++){
        if(a[i] <= 0 && a[i+1] > 0) pos = i;
    }
    int res = inf, rmax = n - pos;
    if(a[1] > 0) cout << a[k] << endl;
    else{
        for(int i=1;i<=pos;i++){
            int l = pos - i + 1;
            if(l > k) continue;
            int r = k - l;
            if(r > rmax) break;
            if(r == 0) res = min(res, abs(a[i]));
            else res = min(res, min(2*abs(a[i]) + a[pos+r], 2*a[pos+r]+abs(a[i])));
        }
        cout << res << endl;
    }
    return 0;
}

 

标签：cout,int,Candles,pos,abs,res
From： https://www.cnblogs.com/zmogu/p/16630004.html