【Luogu】【关卡2-6】贪心（2017年10月）

任务说明：贪心就是只考虑眼前的利益。对于我们人生来说太贪是不好的，不过oi中，有时是对的。

P1090 合并果子

有N堆果子，只能两两合并，每合并一次消耗的体力是两堆果子的权重和，问最小消耗多少体力。

直接贪心，每次取两堆权重最小的果子合并，注意不能在一个for循环里面sort，这样是O(N^2logN)；会TLE。

我AC的方法是第一遍sort，在循环里面用插入排序。（也有其他方法用优先队列，二叉堆什么的，不会写）

poj有个一样的题目3253 Fence Repair。然后shi哥那本书里也有讲这个题。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <vector>

 #include <cstring>

 #include <map>

 #include <climits>

 #include <algorithm>

 #include <cmath>

 #include <sstream>

 using namespace std;

 const int INF = ;

 /*

 void print(vector<int>& vec) {

     printf("==========begin debug========\n");

     for(auto ele : vec) {

         printf("%d ", ele);

     }

     printf("\n\n");

 }

 */

 int main() {

     int n;

     cin >> n;

     vector<int> vec(n);

     for(int i = ; i < n; ++i) {

         cin >> vec[i];

     }

     long long ans = ;

     //[1]快排

     sort(vec.begin(), vec.end());

     //[2]里面做插入排序

     for(int i = ; i < n; ++i) {

         int b = vec[i-] + vec[i];

         vec[i] = b, vec[i-] = ;

         ans += b;

         int j = i + ;

         while( j < n && vec[j] <= b) {

             vec[j-] = vec[j];

             ++j;

         }

         vec[j-] = b;

         //print(vec);

     }

     cout << ans << endl;

     return ;

 }

P1181 数列分段Section I

给一个n个元素的数组，和一个数字m，问最少能把这个数组分成几段，每段的和小于等于m。

直接贪心。

第一次提交全WA。注意写法。这种题目一层循环就好了，写两层完全错。

第二次提交AC了。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <vector>

 using namespace std;

 int main() {

     int ans = ;

     int n;

     long long m;

     cin >> n >> m;

     vector<long long> vec(n);

     for(int i = ; i < n; ++i) {

         cin >> vec[i];

     }

     int start = ;

     long long summ = ;

     for (int i = start; i < n; ++i) {

         if (summ + vec[i] > m) {

             ++ans;

             summ = ;

             --i;

         } else {

             summ += vec[i];

         }

     }

     if (summ != ) {

         ++ans;

     }

     cout << ans << endl;

     return ;

 }

P1208 [USACO1.3]混合牛奶 Mixing Milk

简单题直接做了

巴特西

【Luogu】【关卡2-6】贪心（2017年10月）

最新文章

热门文章