开机方案题解

题目描述

h 学长有个机器用来完成任务。
现在有 n 个任务，第 i 个任务（1<= i <= n) 在 ti 时刻开始，并在 ti + 1 时刻结束。同一时刻不会有多个任务。 h 学长可以在任何时刻开启机器，不过每一次开启机器都会消耗 1 点能量。h 学长只有 k 点能量可以用于开启机器。但是机器开着的时候需要消耗燃料，显然让机器一直开着并不一定是最好的选择。
现在 h 学长想利用自己具备的 k 点能量，有效的控制机器的开启，使得机器完成 n 个任务消耗的燃料尽可能的少。那么对应给出的 n 个任务以及 h 学长拥有的能量数，你能帮帮他吗？
提示：消耗的燃料要尽可能的少，即机器工作的时间尽可能的短。

输入格式:
第一行包括两个整数 n和 k（1<= n <= 1e5, 1<= k <=n） ，表示有 n 个任务和 h 学长拥有 k 点能量。
接下来 n 行，每行一个整数 ti（1<= ti <=1e9），表示第 i 个任务在 ti 时刻开始，并在 ti + 1 时刻结束 。

输出格式:
输出一行包含一个整数，表示机器工作的最少时间。

解题思路

1.相邻任务的时间间隔为 x[i]=t[i]-(t[i-1]+1)
2.机器第一次开启与最后一次关闭的时间差为 ans
3.对时间间隔排序，选择（k-1）个较大的时间间隔关闭机器，
即用 ans -（k-1）个较大的时间间隔

完整代码

#include<stdio.h>
#include<algorithm>
using namespace std;

int main()
{
	int n, k, i, j, ans;
	int t[100020], x[100020] = { 0 };
	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++) {
		scanf("%d", &t[i]);
		if (i != 0) {
			x[i] = t[i] - (t[i - 1] + 1);
		}/*xi为每两个任务的时间间隔*/
	}
	sort(x, x + n);
	ans = t[n - 1] - t[0] + 1;
	for (i = 1, j = n - 1; i <= k - 1 ; i++, j--) {
		ans -= x[j];
	}/*总任务时间扣除k-1个较大时间间隔*/
	printf("%d", ans);
	return 0;
}