首页 > 代码库 > 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(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。