Dain

写出一个可以工作的程序并不够

统计

留言簿(3)

积分与排名

良师益友

阅读排行榜

评论排行榜

3017

#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

struct Node {
    int i,j;
    int value;
};

long num[100000];
vector<Node> matrix;

int main() {
    long n;
    long long m;
    scanf("%ld %lld",&n,&m);

    long i,j;
    for(i = 0;i < n;++i) {
        scanf("%ld",&num[i]);
    }

    for(i = 0;i < n;++i) {
        if(num[i] > m) {
            break;
        }
    }

    if(i < n) {
        printf("-1\n");

        return 0;
    }

    long long res = -1;
    long long sum;
    long max,min = 0;
    for(i = 0;i < n;++i) {
        if(i > 0) {
            min = 1000000;
            for(j = 0;j < matrix.size();++j) {
                if(matrix[j].j == i - 1 && matrix[j].value < min) {
                    min = matrix[j].value;
                }
            }
        }
        else {
            min = 0;
        }

        sum = 0;
        Node node;
        max = -1;
        for(j = i;j < n;++j) {
            sum += num[j];
            if(sum <= m) {
                if(max < num[j]) {                    
                    max = num[j];
                }
                node.i = i;
                node.j = j;
                node.value = max + min;
                matrix.push_back(node);
                if(j == n - 1) {
                    if(res != -1) {
                        if(node.value < res) {
                            res = node.value;
                        }
                    }
                    else {
                        res = node.value;
                    }
                }
            }
            else {
                break;
            }
        }
    }
    
    printf("%lld\n",res);

    return 0;
}

posted on 2007-05-25 10:06 Dain 阅读(263) 评论(0)  编辑 收藏 引用 所属分类: 笔记


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理