求助,为什么你们二分法分出来结果是对的
查看原帖
求助,为什么你们二分法分出来结果是对的
874984
ho33楼主2022/11/28 20:57

就拿样例来说,我的二分法明显告诉我只要和数是5以上,那么都可以成立,但是5不是任何组合的和,我应该如何加个条件让二分法分出来的答案正好为最小的和```c #include<stdio.h> #include<string.h> #include<stdbool.h> bool check(int mid,int arr,int n,int m) { int sum = 0; for (int i = 0; i < n;i++) { sum += arr[i]; if(sum >= mid) { / if(sum == mid) { flag = 1; } */ m--; sum = 0; } } if(m>=0) { return true; } return false; } int main() { int N = 0, M = 0; int arr[10002]; memset(arr, 0, sizeof(arr)); scanf("%d%d",&N,&M); for (int i = 0; i < N;i++) { scanf("%d", &arr[i]); } //二分答案的查询 int left = 0; int right = 100; while(left < right) { int mid = left + (right - left) / 2; if(check(mid,arr,N,M - 1)) { right = mid; } else { left = mid + 1; } } printf("%d",left+1); }

2022/11/28 20:57
加载中...