频道栏目
首页 > 考试 > 其他 > 正文

Wooden Sticks(贪心)问题解析

2018-03-10 10:00:17      个评论    来源:铭 の ブロゲ  
收藏   我要投稿

题目描述


There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:

(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l’ and weight w’ if l<=l’ and w<=w’. Otherwise, it will need 1 minute for setup.

You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5), and (1,4), then the minimum setup time should be 2 minutes since there is a sequence of pairs (1,4), (3,5), (4,9), (2,1), (5,2).

输入


3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1

输出


2
1
3

源代码

#include
using namespace std;
#include
#include
struct M {
    int x, y;
};
bool Comp(const int &a, const int &b)
{
    if (a != b)return a > b;
    else return a > b;
}
int main()
{
    vectorv(5000);
    int m, n;
    cin >> m;
    for (int i = 0;i < m;i++)
    {
        cin >> n;
        for (int j = 0;j < n;j++)
        {
            cin >> v[j].x >> v[j].y;
        }
        //数据处理
        for (int j = 0;j < n - 1;j++)
        {
            for (int z = 0;z < n - 1 - j;z++)
            {
                if (v[z].x < v[z + 1].x)
                {
                    swap(v[z], v[z + 1]);
                }
                else if (v[z].x == v[z + 1].x)
                {
                    if (v[z].y < v[z + 1].y)
                    {
                        swap(v[z], v[z + 1]);
                    }
                }
            }
        }//将数据按照长度优先,重量次之的顺序重新排列完毕
        int ans = 1, example = v[0].y;
        for (int i = 0;i < n - 1;i++)
        {
            if (example < v[i + 1].y)
            {
                ans += 1;
                example = v[i + 1].y;
            }
        }//以重量为参考,example变量保存最大值,如果出现更大值,则赋给example,同时,ans++
        cout << ans << endl;
    }
}
上一篇:The nearest taller cow
下一篇:二叉树的深度--Java实现
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站