第17回情報オリンピック本戦過去問1
JOI君の部屋にはストーブがある．JOI君自身は寒さに強いのでひとりで部屋にいるときはストーブをつける必要はないが，来客があるときはストーブをつける必要がある．
この日，JOI君のもとには $ N 人の来客がある．$ i 番目 $ (1 \leqq i \leqq N) の来客は時刻 $ T_i に到着し，時刻 $ T_i + 1 に退出する．同時に複数人の来客があることはない．
JOI君は任意の時刻にストーブをつけたり消したりできる．ただし，ストーブをつける度にマッチを1本消費する．JOI君はマッチを $ K 本しか持っていないので，$ K 回までしかストーブをつけることができない．一日のはじめにストーブは消えている．
ストーブをつけているとその分だけ燃料を消費するので，ストーブをつけたり消したりする時刻をうまく定めて，ストーブがついている時間の合計を最小化したい．
課題
JOI君の部屋への来客の情報と，JOI 君の持っているマッチの本数が与えられたとき，ストーブがついている時間の合計の最小値を求めよ．
入力
標準入力から以下の入力を読み込め．
1行目には，2つの整数 $ N, K が空白を区切りとして書かれている．これは，JOI君の部屋に $ N 人の来客があり，JOI君は $ K 本のマッチを持っていることを表す．
続く $ N 行のうちの $ i 行目 $ (1 \leqq i \leqq N) には，整数 $ T_i が書かれている．これは，$ i 番目の来客が時刻 $ T_i に到着し，時刻 $ T_i + 1 に退出することを表す．
出力
標準出力に，ストーブがついている時間の合計の最小値を1行で出力せよ．
制限
すべての入力データは以下の条件を満たす．
$ 1 \leqq N \leqq 100000.
$ 1 \leqq K \leqq N.
$ 1 \leqq T_i \leqq 1000000000 \quad (1 \leqq i \leqq N).
$ T_i < T_{i+1} \quad (1 \leqq i \leqq N - 1).
ものすごく単純な答え
code:test.c
int stove(int n, int t[], int a[])
{
int i, s, p;
s = 0;
for (i = 1; i < n; i++) {
}
}
return s;
}
int main(void)
{
int n, k, i, m, s, smin;
scanf("%d%d", &n, &k);
for (i = 0; i < n; i++) {
}
for (i = 1; i < n; i++) {
}
do {
m = 0;
for (i = 0; i < n; i++) {
}
if (m == k) {
s = stove(n, t, a);
/*
for (i = 0; i < n; i++) {
}
printf(": %d\n", s);
*/
if (s < smin) {
smin = s;
}
}
i = 1;
while (i < n && ++ai == 2) { i++;
}
} while (i < n);
printf("%d\n", smin);
return 0;
}
データ例：
code:test.txt
10 5
7 56 129 187 217 289 333 411 434 443
これで ./a.out <test.txt のようにして実行すると 160 を出力する。