Monthly Expense
Time Limit:2000MS |
|
Memory Limit:65536K |
Total Submissions:7707 |
|
Accepted:3180 |
Description
Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤moneyi≤ 10,000) that he will need to spend each day over
the nextN(1 ≤N≤ 100,000) days.
FJ wants to create a budget for a sequential set of exactlyM(1 ≤M≤N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.
FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.
Input
Line 1: Two space-separated integers:NandM
Lines 2..N+1: Linei+1 contains the number of dollars Farmer John spends on theith day
Output
Line 1: The smallest possible monthly limit Farmer John can afford to live with.
Sample Input
7 5
100
400
300
100
500
101
400
Sample Output
500
题目大意:知道农民接下来N天每天花的钱,不改变顺序要分成M份。求最大一份的最小值是多少。
二分查找,代码:
#include<iostream>
using namespace std;
int i,j,n,m,cxb[100010];
bool fine(int a)
{
int temp=0,x=1;
for(i=1;i<=n;i++)
{
if(x>m)
return false;
temp+=cxb[i];
if(temp>a)
{
temp=cxb[i];
x++;
}
}
if(x<=m)
return true;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int sum=0,min=0,max,mid;
for(i=1;i<=n;i++)
{
scanf("%d",&cxb[i]);
sum+=cxb[i];
if(cxb[i]>min)
min=cxb[i]; //最小为花的最多的那天
}
max=sum;//最大为总的钱数
int ans;
while(max>=min)//进行二分查找
{
mid=(max+min)/2;
if(fine(mid))
{
max=mid-1;
ans=mid;
}
else
{
min=mid+1;
}
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
北大POJ3273-Monthly Expense POJ3273-Monthly Expense
poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
POJ-3299解题 C++源代码 Description Adapted from Wikipedia, the free encyclopedia The humidex is a measurement used by Canadian meteorologists to reflect the combined effect of heat and humidity. It...
西北工业大学-c语言-POJ-题目及答案-第七季.doc
poj-2528 Mayor's posters 测试数据及答案
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
算法-炮兵阵地(POJ-1185)(包含源程序).rar
算法-开关问题(POJ-1830)(包含源程序).rar
算法-青蛙的约会(POJ-1061)(包含源程序).rar
北大POJ2002-Squares 解题报告+AC代码
POJ - 2136. VerticalHistogram(统计字母个数)题目链接题目就是给你四行字符串,然后要你统计大写字母(只有大写字母)的个数,然后以特定
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501