贪心

admin管理员组

文章数量:1026989

贪心

题目：

=3273

题意：

给定一组序列N个数字，初始时各自为一个集合，相邻集合可以合并，记合并结果为M个集合时，每个集合的元素之和的最大值为s，求s的最小值

思路：

贪心枚举+二分搜索

思路同POJ3258 可参见另一篇题解，不同之处在于本题求最小的最大值，而3258求最大的最小值，所以，本题最后应输出 low，而不是high

另外，low的初始情况应为所有元素中最大元素的值，我一开始把low赋值为0，一直出错，因为当N=M时，这种初始条件会恒输出0

代码：

#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<functional>
//#pragma comment(linker, "/STACK:102400000,102400000")//C++
using namespace std;const int MAXINT = 0x7fffffff;
const int MAXSIZE = 100000 + 5;int main(){int n,m;int arr[MAXSIZE];long long low=0;long long high=0;cin>>n>>m;for (int i=0;i<n;++i){cin>>arr[i];high+=arr[i];}//cout<<low<<endl<<high<<endl;while (low<=high){long long mid=(low+high)>>1;int faj=1;long long sum=arr[0];//cout<<"low:"<<low<<" high:"<<high<<" mid:"<<mid;for (int i=1;i<n;++i){if (sum+arr[i]>mid){++faj;sum=arr[i];}else {sum+=arr[i];}}//cout<<" faj:"<<faj<<endl;if (faj>m){low=mid+1;}else{high=mid-1;}}cout<<low<<endl;return 0;
}

贪心

题目：

=3273

题意：

给定一组序列N个数字，初始时各自为一个集合，相邻集合可以合并，记合并结果为M个集合时，每个集合的元素之和的最大值为s，求s的最小值

思路：

贪心枚举+二分搜索

思路同POJ3258 可参见另一篇题解，不同之处在于本题求最小的最大值，而3258求最大的最小值，所以，本题最后应输出 low，而不是high

另外，low的初始情况应为所有元素中最大元素的值，我一开始把low赋值为0，一直出错，因为当N=M时，这种初始条件会恒输出0

代码：

#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<functional>
//#pragma comment(linker, "/STACK:102400000,102400000")//C++
using namespace std;const int MAXINT = 0x7fffffff;
const int MAXSIZE = 100000 + 5;int main(){int n,m;int arr[MAXSIZE];long long low=0;long long high=0;cin>>n>>m;for (int i=0;i<n;++i){cin>>arr[i];high+=arr[i];}//cout<<low<<endl<<high<<endl;while (low<=high){long long mid=(low+high)>>1;int faj=1;long long sum=arr[0];//cout<<"low:"<<low<<" high:"<<high<<" mid:"<<mid;for (int i=1;i<n;++i){if (sum+arr[i]>mid){++faj;sum=arr[i];}else {sum+=arr[i];}}//cout<<" faj:"<<faj<<endl;if (faj>m){low=mid+1;}else{high=mid-1;}}cout<<low<<endl;return 0;
}

本文标签： 贪心