最大值最小化

 1 #include<stdio.h>
 2 
 3 int a[10000];
 4 int n,m;
 5 
 6 int is_part(int u)
 7 {
 8     int sum,i,count,ok;
 9     sum=count=0;ok=1;
10     for(i=0;i<n;i++)
11     {
12         if(a[i]>u)
13         {
14             ok=0;
15             break;
16         }
17         if(sum+a[i]>u) 
18         { 
19             sum=a[i],
20             count++;
21             if(count==m)
22             {
23                 ok=0;
24                 break;
25             }
26         }
27         else    sum+=a[i];
28     }
29     return ok;
30 }
31 
32 
33 int fun(int x,int y)
34 {
35     int m;
36     while(x<y)
37     {
38         m=x+(y-x)/2;
39         if(is_part(m)) y=m;
40         else x=m+1;
41     }
42     return x;
43 }
44 
45 int main()
46 {
47     int i,j,max,sum;
48     while(scanf("%d%d",&n,&m)!=EOF)
49     {
50         max=sum=0;
51         for(i=0;i<n;i++)
52         {
53             scanf("%d",&a[i]);
54             max=max>a[i]?max:a[i];
55             sum+=a[i];
56         }
57         j=fun(max,sum);
58         printf("%d\n",j);
59         sum=0;
60         for(i=0;i<n;i++)
61         {
62             sum+=a[i];
63             if(sum>j) 
64             {
65                 sum=a[i];
66                 printf("| ");
67             }
68             printf("%d ",a[i]);
69         }
70         printf("\n");
71     }
72     return 0;
73 }
74             
75 /*
76 6 3
77 1 2 3 2 5 4
78 
79 
80 7
81 1 2 3 | 2 5 | 4
82 */

 1 #include<stdio.h>
 2 
 3 int a[10000];
 4 int n,m;
 5 
 6 int is_part(int u)
 7 {
 8     int sum,i,count,ok;
 9     sum=count=0;ok=1;
10     for(i=0;i<n;i++)
11     {
12         if(a[i]>u)
13         {
14             ok=0;
15             break;
16         }
17         if(sum+a[i]>u) 
18         { 
19             sum=a[i],
20             count++;
21             if(count==m)
22             {
23                 ok=0;
24                 break;
25             }
26         }
27         else    sum+=a[i];
28     }
29     return ok;
30 }
31 
32 
33 int fun(int x,int y)
34 {
35     int m;
36     while(x<y)
37     {
38         m=x+(y-x)/2;
39         if(is_part(m)) y=m;
40         else x=m+1;
41     }
42     return x;
43 }
44 
45 int main()
46 {
47     int i,j,max,sum;
48     while(scanf("%d%d",&n,&m)!=EOF)
49     {
50         max=sum=0;
51         for(i=0;i<n;i++)
52         {
53             scanf("%d",&a[i]);
54             max=max>a[i]?max:a[i];
55             sum+=a[i];
56         }
57         j=fun(max,sum);
58         printf("%d\n",j);
59         sum=0;
60         for(i=0;i<n;i++)
61         {
62             sum+=a[i];
63             if(sum>j) 
64             {
65                 sum=a[i];
66                 printf("| ");
67             }
68             printf("%d ",a[i]);
69         }
70         printf("\n");
71     }
72     return 0;
73 }
74             
75 /*
76 6 3
77 1 2 3 2 5 4
78 
79 
80 7
81 1 2 3 | 2 5 | 4
82 */