http://codeforces.com/problemset/problem/747/D
题意：有n天，k次使用冬天轮胎的机会，无限次使用夏天轮胎的机会，如果t<=0必须使用冬轮，其他随意。问最少的换胎次数。
思路：先数冬天的天数tol，如果天数>k的话，那么就不可能度过。否则，最坏情况下，每到冬天就换一次冬天轮胎，然后度过冬天就换夏天轮胎，所以答案ans = 2*tol。然后考虑尽量让每段冬天连续，这样可以减少换胎次数，于是算出冬天之间的间隔，然后从小到大排序，每次减少一段间隔，ans就可-2。然后考虑特殊情况，如果最后一次换冬天轮胎，可以用到结束，那么ans-1。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define INF 0x3f3f3f3f
#define N 200010
typedef long long LL;
vector<int> vec;
int t[N];
int main() {
int n, k;
cin >> n >> k;
int tol = , ans = ;
int pre = -, last = -;
for(int i = ; i <= n; i++) {
scanf("%d", &t[i]);
if(t[i] < ) {
last = i; // 最后一次冬天
ans += ;
tol++;
if(pre != -)
vec.push_back(i - pre - ); // 处理冬天间隔
pre = i;
}
} k -= tol;
if(k < ) {
puts("-1");
} else {
sort(vec.begin(), vec.end());
for(int i = ; i < vec.size(); i++) {
if(k - vec[i] >= ) {
k -= vec[i];
ans -= ;
} else break;
}
if(n - last <= k) ans--;
printf("%d\n", ans);
}
return ;
}