題目描述
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;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/43034.html
標籤：C
下一篇：母函式及其應用