题解 P2884 【[USACO07MAR]每月的费用Monthly Expense】

难得的一次过的题 这道题是典型的二分答案加贪心策略（求最大值（最大fajo月的预算）的最小值）： 先找到答案区间（在每个月的最大值和所有月的总和之间） 然后利用二分查找答案 精髓是check函数（详细过程注释已经讲明白了） 注意的是第一次查找到的解不一定是最优解，所以要定义ans来存储最优解 最后输出就好了 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int n,m,a[100001];//n天,m组,a[i]表示第i天的钱 int read()//读入优化 { char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); int h=0; while(ch>='0'&&ch<='9') { h=h*10+ch-48; ch=getchar(); } return h; } int check(int max1),q[100001]; int main()//求最大的最小值 { n=read(); m=read(); int l=0,r=0,ans; for(int i=1;i<=n;i++) { a[i]=read(); q[i]=q[i-1]+a[i];//定义前缀和 l=l>a[i]?l:a[i];//答案左区间应为最大的一个月 r+=a[i];//答案右区间应为每个月经费之和 } while(l<=r) { int mid=(l+r)/2,k=check(mid); if(k==1)//如果满足条件了，就记录此时的解（此时的解一定比之前查找到的更优，因为如果查到了解，就会在数值更大的区间内寻解） { ans=mid; r=mid-1;//在数值更大的区间内寻解 } else l=mid+1;//在数值更小的区间内寻解 } cout<<ans; return 0; } int check(int max1)//max1:一个fajo月(财政周期)的总经费的最大值 { int s,f; int tot=1;//表示划分的财政周期数 for(s=1;s<=n;s=f)//枚举起始月 { for(f=s+1;f<=n;f++)//枚举结束月 { if(q[f]-q[s-1]<=max1) continue;//如果这个周期内总额没超过查找到的答案，就继续加上下一个月 else//超过了就再加一个fajo月(贪心策略) { tot++;//新增一个fajo月 break;//再次枚举起始月 } } } if(tot<=m) return 1;//满足条件返回1 else return 0; } ```