Wooden Sticks
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8899 Accepted Submission(s): 3630
【解题思路】初学贪心仅知道一些理论的知识,这题说是贪心自己也没啥感觉,做题的思路是在抛开贪心的概念然后按照自己的想法实现出来,实现之后想在思路中找到贪心的影子,只能看到每次都是找尽可能多的stick仅此而已,Pursuiting...
Wa的原因是当时没考虑到stick的选择可以是不连续的,直接将排序后的次元素的比较上将后面一个跟前面一个进行比较。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define SIZE 5002 using namespace std; typedef struct sticks{
int L, w;
}sticks;
sticks stick[SIZE];
bool visit[SIZE];
int n; bool cmp(const sticks& a, const sticks& b)
{
if(a.w == b.w)
return a.L < b.L;
else return a.w < b.w;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int T, sum;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i=; i<n; ++i)
scanf("%d%d", &stick[i].L, &stick[i].w);
sort(stick, stick+n, cmp);
sum = ;
memset(visit, false, sizeof(visit));
int curmax = ;
for(int i=; i<n; ++i)
{
if(visit[i]) continue;
curmax = stick[i].L;
sum++;
for(int j=i+; j<n; ++j)
{
if(!visit[j] && stick[j].L >= curmax)
{
visit[j] = true;
curmax = stick[j].L;
}
}
}
/* for(int i=0; i<n; ++i)
if(!i || stick[i].L<stick[i-1].L) sum++;
*/
printf("%d\n", sum);
}
return ;
}
HDU ACM 1051/ POJ 1065 Wooden Sticks的更多相关文章
-
POJ 1065 Wooden Sticks / hdu 1257 最少拦截系统 DP 贪心
参考链接:http://blog.csdn.net/xiaohuan1991/article/details/6956629 (HDU 1257 解题思路一样就不继续讲解) POJ 1065题意:给你 ...
-
POJ 1065 Wooden Sticks
Wooden Sticks Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 16262 Accepted: 6748 Descri ...
-
POJ 1065 Wooden Sticks (贪心)
There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The st ...
-
POJ 1065 Wooden Sticks(zoj 1025) 最长单调子序列
POJ :http://poj.org/problem?id=1065 ZOJ: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId= ...
-
poj -1065 Wooden Sticks (贪心or dp)
http://poj.org/problem?id=1065 题意比较简单,有n跟木棍,事先知道每根木棍的长度和宽度,这些木棍需要送去加工,第一根木棍需要一分钟的生产时间,如果当前木棍的长度跟宽度 都 ...
-
poj 1065 Wooden Sticks 【贪心 新思维】
题目地址:http://poj.org/problem?id=1065 Sample Input 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 ...
-
POJ 1065 Wooden Sticks【贪心】
题意: 有一些木棍,每个有长度和重量,要求把这些木棍排成若干两个属性值均不下降的序列.问至少要分为多少个序列.且要保证排出来的子序列数最少. 思路: ( 9 , 4 ) ,( 2 , 5 ) ,( 1 ...
-
POJ 1065 Wooden Sticks Greed,DP
排序后贪心或根据第二关键字找最长下降子序列 #pragma comment(linker, "/STACK:1024000000,1024000000") #include< ...
-
POJ 1065 Wooden Sticks#贪心+qsort用法
(- ̄▽ ̄)-* 这道题用到了cstdlib库的qsort()函数: 用法链接:http://www.cnblogs.com/syxchina/archive/2010/07/29/2197382.h ...
随机推荐
-
Python error: Unable to find vcvarsall.bat
在安装一些Python模块时,大部分是cpython写的模块时会发生如下错误 error: Unable to find vcvarsall.bat.先前的一篇文章:在Windows上安装Scrapy ...
-
jquery back to top 页面底部的返回顶部按钮
<!doctype html> <html lang="en"> <head> <meta charset="UTF-8&quo ...
-
bootstrap-图文混排 media
<!-- media 图文混排 media-left(right) 图片的区域 在左边显示(右边) media-body 内容区域 media-heading 内容区域里的标题 media-mi ...
-
ACM Computer Factory
ACM Computer Factory Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6104 Accepted: 2113 ...
-
【LEETCODE OJ】Copy List with Random Pointer
Problem link: http://oj.leetcode.com/problems/copy-list-with-random-pointer/ Deepcopy a linked list ...
-
poj 3295 Tautology
点击打开链接 Tautology Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8127 Accepted: 3115 ...
-
hud 1241 Oil Deposits
Oil Deposits Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Tot ...
-
java.lang.ClassCastException: sun.proxy.$Proxy11 cannot be cast to分析
报这个错,只有一个原因,就是你转化的类型不对. 如果你的类是一个单实体类,也就是没有继承或是接口别的类. public class HjmServiceImpl {} 那么这样写就可以: HjmSer ...
-
Freescale MKL16Z1288VF4 芯片调试接口
WDOG监视内部系统操作,并在发生故障时强制复位.它可以运行在一个独立的1 kHz低功率振荡器,具有可编程刷新窗口,以检测程序流或系统频率的偏差. 看门狗计时器保持一个时间在系统上运行,并重置它,以防 ...
-
【笔记】Python基础四:迭代器和生成器
一,迭代器协议和for循环工作机制 (一),迭代器协议 1,迭代器协议:对象必须提供一个next方法,执行该方法要么返回迭代中的下一项,要么就引起一个stopiteration异常,以终止迭代(只能往 ...