pku3273 Monthly Expense

http://poj.org/problem?id=3273

二分查找

一个数组大小为n，分成连续的m部分，求和最大的那个部分

把n分成m部分，由于弱菜代码能力比较差，处理下标问题很晕。。。改用“栈”模拟，不用考虑下标问题

#include <stdio.h>
#include <stack>

#define N 100100

using namespace std;

int n, a[N];

int need(int x)
{
    int i, temp;
    stack<int> s;
    for(i=1; i<=n; i++)
    {
        if(s.empty() || s.top()+a[i]>x)
        {
            s.push(a[i]);
        }
        else
        {
            temp = s.top();
            s.pop();
            s.push(temp+a[i]);
        }
    }
    return (int)s.size();
}

int bs(int l, int r, int x)
{
    int m;
    while(l < r)
    {
        m = (l+r)>>1;
        //need函数单调递减，求第一个函数值小于等于x的数
        if(need(m) > x)
        {
            l = m+1;
        }
        else
        {
            r = m;
        }
    }
    return l;
}

int main()
{
    int m, i, l = 0, r = 0;
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++)
    {
        scanf("%d", a+i);
        if(a[i] > l)
        {
            l = a[i];
        }
        r += a[i];
    }
    printf("%d\n", bs(l, r, m));
    return 0;
}