题解 P7666 [JOI2018] Stove

· · 题解

供题人前来报到，现分享自己的解题思路及代码、官方解题代码、双倍经验告知。
题目传送>>P7666。

题意简述

JOI 君会在家中有客人时开着可随时开关闭的炉子。现他有 K 根可开炉子的火柴，将有 N 名客人分别在已知的特定时刻 T_i 前来并在 T_i+1 离开，求炉子最短总运行时间。

题目分析：

因为客人在的时刻是零零散散的，所以就会存在一些无客人的时间间隔，而要想使炉子运行总时间最短，那么我们应尽可能地在合适的时刻及时关闭炉子，避免在无客人时造成炉子浪费，即尽可能做到只有有客人在时炉子才开着。而在下一次来客人时再打开炉子是需要消耗火柴的，而火柴数量又有限，所以有时我们可能需要保持炉子运行（即使此时无客人）。
当第一位客人前来时我们必须消耗一根火柴打开炉子，但如果一直保持运行到最后一名客人走显然是不理智的。我们需要尽可能的避免较长时间无客人间隔运行炉子，此时我们就可在当前客人走时关闭炉子，在下一名客人来时再开炉子。即每多一根火柴，我们就可尽可能的避免一个无客间隔浪费。
综上分析，我们可以分别计算各无客间隔时长（共 N-1 个无客间隔），然后优先依靠炉子关开避免较大无客间隔期间的浪费。

Code1(己)：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,k;   //定义客人数、火柴数 
int a[100010],b[100010];   //开数组存各客人前来的时刻、各无客间隔时长 
int ans=0;   //定义炉子运行总时长 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k; 
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    ans+=a[n]-a[1]+1;   //如不能避免无客间隔的全程时长 
    for(int i=1;i<n;i++)
    {
        b[i]=a[i+1]-a[i]-1;   //分别计算各无客间隔时长
    }
    sort(b+1,b+n);   //对各无客间隔时长排序（默认递增） 
    for(int i=n-1;i>=n-k+1;i--)   //因为递增排的序所以回着循环 ，注意共n-1个间隔，共k根火柴 
    {
        ans-=b[i];   //优先依靠炉子关开避免较大无客间隔期间的浪费并，减去间隔时长 
    }
    cout<<ans;  
    return 0;
}

Code2(官方)（C++11及以上）：

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define PB push_back

using vi=vector<int>;

int read(){
    int i;
    scanf("%d",&i);
    return i;
}

int main(){
    int n=read(),k=read();
    int mn,mx,last;
    vi len;
    REP(i,n){
        int t=read();
        if(i==0)mn=t;
        if(i==n-1)mx=t+1;
        if(0<i)len.PB(t-last-1);
        last=t;
    }
    sort(len.begin(),len.end(),greater<int>());
    int ans=mx-mn;
    REP(i,k-1)ans-=len[i];
    cout<<ans<<endl;
}

结果（己）（未吸氧）：

双倍经验

本供题人在供此题时即发现了此题与之前做过的一题基本同思路，现分享双倍经验>>P1209 [USACO1.3]修理牛棚 Barn Repair，区别即为后者输入数据多了一个无关变量且输入数据可能无序需多一次排序。
企鹅的题解到此结束，祝各位 OIers 进步 ++~