当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

USACO Barn Repair 题解

发表于: 2013-04-26   作者:bbsunchen   来源:转载   浏览次数:
摘要: 题目翻译还是看USACO吧, 这题贪心,贪心都是很水的,还有解析说用动态规划做的,是因为题目太水让你脑子进水了吧? 下面是代码,忍不住用STL /* ID: bbsunch2 PROG: barn1 LANG: C++ */ #include <iostream> #include <fstream> #include <string> #

题目翻译还是看USACO吧,

这题贪心,贪心都是很水的,还有解析说用动态规划做的,是因为题目太水让你脑子进水了吧?

下面是代码,忍不住用STL

/*
ID: bbsunch2
PROG: barn1
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <stdlib.h>
#include <algorithm>

using namespace std;

int main()
{
    ofstream fout ("barn1.out");
    ifstream fin ("barn1.in");

    int boardNum = 0;
    int stallNum = 0;
    int cowStall = 0;
    fin >> boardNum >> stallNum >> cowStall;
    //cout << boardNum << stallNum << cowStall << endl;
    vector <int> stall;
    vector<int> gap;
    for(int i = 0; i < cowStall; i++)
    {
        int s;
        fin >> s;
        stall.push_back(s);
    }
    sort(stall.begin(), stall.end());
    int former = 0;
    former = stall[0];
    for(int i = 1; i < stall.size(); i++)
    {
        int latter = stall[i];

        if(latter - former > 1)
        {
            //cout << former << " " << latter << endl;
            gap.push_back(latter - former - 1);
        }
        former = latter;
    }
    //cout << gap.size() << endl;
    //for(int i = 0; i < gap.size(); i++)
    //{
    //    cout << gap[i] << endl;
    //}
    sort(gap.begin(), gap.end());
    //cout << "test" << endl;
    //cout << gap.size() << endl;

    int gapNum = boardNum - 1;

    if(gapNum > gap.size())
    {
        gapNum = gap.size();
    }
    for(int i = 0; i < gapNum; i++)
    {
        gap.erase(gap.end()-1);
    }

    for(int i = 0; i < gap.size(); i++)
    {
        cowStall += gap[i];
    }
    fout << cowStall << endl;
    return 0;
}

 

USACO Barn Repair 题解

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
POJ 3168 Barn Expansion扩地:有N块不重叠的矩形地,由左下角(A,B)和右上角(C,D)决定。如果两
【问题描述】 据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出
题意分析: 给出4个长方形的高和长,以及给出6种基本布局,求合成无重叠的最小面积时的长和宽。 解题
估计是因为Win7和ADS不兼容的原因,第一次安装ADS后一直停在100%的位置,等了好久也没有反应。于是
#include <cstdio> #include <iostream> #include <algorithm> using namespace
在写这道题之前,先介绍几点知识。 一、 动态规划(DP) 动态规划(dynamic programming)是求解决策
这道题目,给你一组时间范围,求最大的时间跨度和最大的时间段间隔。题目看似挺简单,但是如果不加
我知道写这东西挺二,可是我确实被USACO的提交折腾了很久…… 首先,它的 TEXT Submitting Solution
Shaping Regions N opaque rectangles (1 <= N <= 1000) of various colors are placed on a
【描述】 给定4个矩形块,找出一个最小的封闭矩形将这4个矩形块放入,但不得相互重叠。所谓最小矩形
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号