方圆网通网站建设公司,天河建设网站方案,凡科网站做商城,网站建设所需服务器把可能的进行二分判断#xff0c;判断的时候尽量向右取#xff0c;一直取到不能去为止#xff0c;这样才有可能成功分割。 判断是否可以把up作为最大值的代码#xff1a; bool judge(LL up){if(up Big) return false; //Big是数组中最大值#xff0c;如果up小于最大值… 把可能的进行二分判断判断的时候尽量向右取一直取到不能去为止这样才有可能成功分割。 判断是否可以把up作为最大值的代码 bool judge(LL up){if(up Big) return false; //Big是数组中最大值如果up小于最大值是不可能成功划分的LL sum 0;int cnt 0;for(int i 0; i n; ){sum 0;while(i n){sum a[i];if(sum up) i;else break;}cnt;}if(cnt k) return true; //成功划分return false;
} 值得注意的是最后得到最小的最大值时应该如何划分题目要求前面的尽量小那么就从后面尽可能多的划分但是不能只满足小于等于up也要考虑到组成k个序列不能让某些序列为空。 AC代码 #includecstdio
#includecstring
#includealgorithm
using namespace std;
typedef long long LL;
const int maxn 500 5;
int a[maxn], vis[maxn];
int Big -1; //Biggest number
int n,k; //Divid n numbers to k squencesbool judge(LL up){if(up Big) return false;LL sum 0;int cnt 0;for(int i 0; i n; ){sum 0;while(i n){sum a[i];if(sum up) i;else break;}cnt;}if(cnt k) return true;return false;
}LL Binary_Search(LL x, LL y){ //[x,y]while(x y){LL mid x (y - x) / 2;bool ok judge(mid);if(ok) y mid;else x mid 1;}return y;
}int main(){int T;scanf(%d, T);while(T--) {memset(vis, 0, sizeof(vis));LL sum 0;Big -1;scanf(%d%d,n,k);for(int i 0; i n; i){scanf(%d,a[i]);sum a[i];Big max(Big, a[i]);}LL up Binary_Search(1, sum);LL div;int cnt 0;for( int i n-1; i 0;){div 0;while(div up i 0 i 1 k - cnt){div a[i];if(div up) --i;}cnt;if(i 0) vis[i] 1;}//print the answerfor(int i 0; i n; i){if(i n-1) printf(%d\n, a[i]);else printf(%d , a[i]);if(vis[i]) printf(/ );}}return 0;
}如有不当之处欢迎指出 转载于:https://www.cnblogs.com/flyawayl/p/8305470.html
