这好像是做的第一道二分,当时完全没思路,参考别人代码以后豁然开朗!
#include <iostream> #include <fstream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <bitset> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> #include <ctime> #define LL long long #define Vi vector<int> #define Si set<int> #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) #define FU(i,a) for(int i(1); i <= (a); i++) #define FD(i,a) for(int i(a); i >= (1); i--) #define FOR(i,a,b) for(int i(a);i <= (b); i++) #define FORD(i,a,b) for(int i(a);i >= (b); i--) #define SET(a,b) memset(a,b,sizeof(a)) #define SD(a) scanf("%d",&(a)) #define LN printf("\n") #define PS printf(" ") #define pb push_back using namespace std; const int maxn=3000; int n,m,a[100001]; int low,high,mid; int solve(int k) { int sum=a[1]; int group=1; FOR(i,2,n) { if(sum+a[i]<=k) sum+=a[i]; else { sum=a[i]; group++; if(group>m) return 1;// 1代表mid太小 } } return -1;//mid 太大 } int main() { SD(n);SD(m); FOR(i,1,n){ SD(a[i]); high+=a[i]; if(low<a[i]) low=a[i]; } mid=(low+high)/2; while(low<high) { int t=solve(mid); if(t==1) //mid is low { low=mid+1; } else { high=mid-1; } mid=(low+high)/2; } printf("%d\n",mid); return 0; }