Wooden Sticks
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 22000 Accepted Submission(s): 8851
(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).
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
1
3
#include "cstdio" #include "iostream" #include "algorithm" #include "string" #include "cstring" #include "queue" #include "cmath" #include "vector" #include "map" #include "stdlib.h" #include "set" #define mj #define db double #define ll long long using namespace std; ; ; ; bool u[N]; typedef struct stu{ int l,w; }M; M s[]; int cmp(M a,M b) { if(a.l==b.l) return a.w>=b.w; return a.l>=b.l; } int main() { int t,n,i,j,ans; scanf("%d",&t); while(t--) { scanf("%d",&n); ;i<n;i++) scanf(; sort(s,s+n,cmp); int mi; ans=; ;i<n;i++) { if(u[i]) continue; mi=s[i].w; ;j<n;j++) { if(!u[j]&&s[j].w<=mi){ mi=s[j].w; u[j]=; } } ans++; } printf("%d\n",ans); } ; }
HDU 1051 Wooden Sticks 贪心||DP的更多相关文章
-
HDU 1051 Wooden Sticks (贪心)
Wooden Sticks Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) To ...
-
HDU - 1051 Wooden Sticks 贪心 动态规划
Wooden Sticks Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) ...
-
HDU 1051 Wooden Sticks 贪心题解
本题一看就知道是最长不减序列了,一想就以为是使用dp攻克了. 只是那是个错误的思路. 我就动了半天没动出来.然后看了看别人是能够使用dp的,只是那个比較难证明其正确性,而其速度也不快.故此并非非常好的 ...
-
hdu 1051 wooden sticks (贪心+巧妙转化)
#include <iostream>#include<stdio.h>#include<cmath>#include<algorithm>using ...
-
hdu 1051:Wooden Sticks(水题,贪心)
Wooden Sticks Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Tot ...
-
HDOJ 1051. Wooden Sticks 贪心 结构体排序
Wooden Sticks Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) To ...
-
HDOJ.1051 Wooden Sticks (贪心)
Wooden Sticks 点我挑战题目 题意分析 给出T组数据,每组数据有n对数,分别代表每个木棍的长度l和重量w.第一个木棍加工需要1min的准备准备时间,对于刚刚经加工过的木棍,如果接下来的木棍 ...
-
HDU 1051 Wooden Sticks 造木棍【贪心】
题目链接>>> 转载于:https://www.cnblogs.com/Action-/archive/2012/07/03/2574800.html 题目大意: 给n根木棍的长度 ...
-
HDU 1051 Wooden Sticks
题意: 有 n 根木棒,长度和质量都已经知道,需要一个机器一根一根地处理这些木棒. 该机器在加工过程中需要一定的准备时间,是用于清洗机器,调整工具和模板的. 机器需要的准备时间如下: 1.第一根需要1 ...
随机推荐
-
WaitType:SOS_SCHEDULER_YIELD
今天遇到一个query,处于SOS_SCHEDULER_YIELD 状态,physical IO 不增加,CPU的使用一直在增长.当一个sql query长时间处于SOS_SCHEDULER_YIEL ...
-
MIT jos 6.828 Fall 2014 训练记录(lab 5)
源代码参见我的github: https://github.com/YaoZengzeng/jos File system perliminaries 我们开发的是一个单用户的操作系统,只提供了足够的 ...
-
Android中的音频播放(MediaPlayer和SoundPool)
Android中音频和视频的播放我们最先想到的就是MediaPlayer类了,该类提供了播放.暂停.停止.和重复播放等方法.该类位于android.media包下,详见API文档.其实除了这个类还有一 ...
-
IPV6与IPV4的区别
IPv4协议的地址长度是32位,IPv6协议的地址长度是128位. 1.表示方式 IPv4地址表示为点分十进制格式,32位的地址分成4个8位分组,每个8位以十进制数显式,中间用点号分隔. 而IPv6采 ...
-
Internal类
C#中一个类中的成员有四种修饰级别: public:完全开放,谁都能访问. private:完全封闭,只有类自身可以访问. internal:只对相同程序集,或使用InternalVisibleToA ...
-
FastStone Capture激活码
用户名:c1ikm注册码:AXMQX-RMMMJ-DBHHF-WIHTV 或 AXOQS-RRMGS-ODAQO-APHUU
-
python学习笔记——(三)文件操作
·集合操作及其相应的操作符表示集合中没有插入,只有添加,因为毕竟无序 #!/usr/bin/env python # -*- coding:utf-8 -*- # Author:Vergil Zhan ...
-
理解es6中的const与“不变”
const实际上保证的,并不是变量的值不得改动,而是变量指向的那个内存地址不得改动. 效果 对于简单类型的数据(数值.字符串.布尔值),值就保存在变量指向的那个内存地址,因此等同于常量. 对于复合类型 ...
-
JavaScript日期排序
//日期排序 function sortDownDate(a, b) { return Date.parse(a.received) - Date.parse(b.received); } funct ...
- XML解析技术简介——(一)