企业网站认证,交互式英语网站的构建,应用之星 wordpress,大专计算机网络技术主要学什么题目链接#xff1a;http://noi.openjudge.cn/ch0111/06/ 总时间限制: 1000ms 内存限制: 65536kB描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。 约翰打算为连续…题目链接http://noi.openjudge.cn/ch0111/06/ 总时间限制: 1000ms 内存限制: 65536kB描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。 约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天每天被恰好包含在一个fajo月里。 约翰的目标是合理安排每个fajo月包含的天数使得开销最多的fajo月的开销尽可能少。 输入 第一行包含两个整数N,M用单个空格隔开。 接下来N行每行包含一个1到10000之间的整数按顺序给出接下来N天里每天的开销。输出 一个整数即最大月度开销的最小值。 样例输入7 5100400300100500101400样例输出500输入输出样例说明 若约翰将前两天作为一个月第三、四两天作为一个月最后三天各自作为一个月则最大月度开销为500。其他任何分配方案都会比这个值更大。 先看AC代码 1 #includestdio.h2 #includestdlib.h3 #includestring.h4 int check(long *a,long N,long long mid,long M); 5 int main()6 {7 long N,M;8 long *aNULL,i;9 long long left0,right0,mid0;
10 int res;
11 12 scanf(%ld%ld,N,M);
13 a(long*)malloc(N*sizeof(long));
14 memset(a,0,N);
15 for(i0;iN;i)
16 {
17 scanf(%ld,a[i]);
18 if(a[i]left) lefta[i];
19 rightrighta[i];
20 }
21
22 while(leftright)
23 {
24 midleft(right-left)/2;
25 rescheck(a,N,mid,M);
26 if(res1) rightmid;
27 else leftmid1;
28 }
29 printf(%lld\n,left);
30 return 0;
31 }
32
33 //假设最大月开销为mid统计需要分成多少个月.然后看月的个数是否太多或太少
34 int check(long *a,long N,long long mid,long M)
35 {
36 long count1,i,temp0;
37 for(i0;iN;i)
38 {
39 if(tempa[i]mid) temptempa[i];//把第i天归入到当前第count月
40 else if(a[i]mid)//可以独立成一个月
41 {
42 count;//开始一个新的月
43 tempa[i];
44 if(countM) return -1;//最大月开销太小导致分的组太多了。
45 }
46 else return -1;//最大月开销mid太小了,导致某些开销比较大的天单独构成一个月都不行。
47 }
48 if(countM) return -1;
49 else if(countM) return 1;//最大月开销mid太大了,导致分的组太少了
50 } 思路说明 题目的意思一定要理解清楚“合理安排每个fajo月包含的天数使得开销最多的fajo月的开销尽可能少。” “输出一个整数即最大月度开销的最小值。” 就是把所有天划分为若干个段先求出每个段里面的数字之和然后统计各段累加和的最大值这个值要尽可能小。现在要找的就是这个“累加和的最大值” 最小可以是多少。 首先这个题目应该二分因为解的区间是可以明确的可以对该区间进行二分求的真正的解。 假设二分的区间left~right其中left是n天开销中最大的那一个数字right是n天开销的总和。 设想一个极限情况要使得每一个月开销尽量小那么每一天都单独做一个月就好啦于是这个时候的月开销最大值就是n天中每天开销最大的值所以left可以取maxa1,......an。 再设想另一种极限情况把所有天合并在一起组成一个月那么这个时候月开销最大值就是sum(a1,a2,......,an)所以right取值就是n天的累加和。 需要注意的一个地方是二分循环部分的代码 1 while(leftright)
2 {
3 midleft(right-left)/2;
4 rescheck(a,N,mid,M);
5 if(res1) rightmid;
6 else leftmid1;
7 }
8 printf(%lld\n,left); 其中leftmid1这里必须加上1否则可能会死循环的。 另外输出值是left。这个地方也要特别注意。请自己脑补为何是left吧 关于子函数check嗯代码注释讲的很清晰不说了。 转载于:https://www.cnblogs.com/huashanqingzhu/p/5607503.html
