首页 > 代码库 > Codeforces 747D:Winter Is Coming(贪心)

Codeforces 747D:Winter Is Coming(贪心)

http://codeforces.com/problemset/problem/747/D

题意:有n天,k次使用冬天轮胎的机会,无限次使用夏天轮胎的机会,如果t<=0必须使用冬轮,其他随意。问最少的换胎次数。

思路:先数冬天的天数tol,如果天数>k的话,那么就不可能度过。否则,最坏情况下,每到冬天就换一次冬天轮胎,然后度过冬天就换夏天轮胎,所以答案是2*tol。然后考虑尽量让每段冬天连续,这样可以减少换胎次数,于是算出冬天之间的间隔,然后从小到大排序,每次减少一段间隔,ans就可-2。然后考虑特殊情况,如果最后一次换冬天轮胎,可以用到结束,那么ans-1。

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <string>
 6 #include <cmath>
 7 #include <queue>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 using namespace std;
12 #define INF 0x3f3f3f3f
13 #define N 200010
14 typedef long long LL;
15 vector<int> vec;
16 int t[N];
17 int main() {
18     int n, k;
19     cin >> n >> k;
20     int tol = 0, ans = 0;
21     int pre = -1, last = -1;
22     for(int i = 1; i <= n; i++) {
23         scanf("%d", &t[i]);
24         if(t[i] < 0) {
25             last = i; // 最后一次冬天
26             ans += 2;
27             tol++;
28             if(pre != -1)
29                 vec.push_back(i - pre - 1); // 处理冬天间隔
30             pre = i;
31         }
32     }
33 
34     k -= tol;
35     if(k < 0) {
36         puts("-1");
37     } else {
38         sort(vec.begin(), vec.end());
39         for(int i = 0; i < vec.size(); i++) {
40             if(k - vec[i] >= 0) {
41                 k -= vec[i];
42                 ans -= 2;
43             } else break;
44         }
45         if(n - last <= k) ans--;
46         printf("%d\n", ans);
47     }
48     return 0;
49 }

 

Codeforces 747D:Winter Is Coming(贪心)