HDU ACM 1051/ POJ 1065 Wooden Sticks

时间:2023-01-02 22:08:08

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的更多相关文章

  1. POJ 1065 Wooden Sticks &sol; hdu 1257 最少拦截系统 DP 贪心

    参考链接:http://blog.csdn.net/xiaohuan1991/article/details/6956629 (HDU 1257 解题思路一样就不继续讲解) POJ 1065题意:给你 ...

  2. POJ 1065 Wooden Sticks

    Wooden Sticks Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 16262 Accepted: 6748 Descri ...

  3. 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 ...

  4. POJ 1065 Wooden Sticks(zoj 1025) 最长单调子序列

    POJ :http://poj.org/problem?id=1065 ZOJ: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId= ...

  5. poj -1065 Wooden Sticks (贪心or dp)

    http://poj.org/problem?id=1065 题意比较简单,有n跟木棍,事先知道每根木棍的长度和宽度,这些木棍需要送去加工,第一根木棍需要一分钟的生产时间,如果当前木棍的长度跟宽度 都 ...

  6. 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 ...

  7. POJ 1065 Wooden Sticks【贪心】

    题意: 有一些木棍,每个有长度和重量,要求把这些木棍排成若干两个属性值均不下降的序列.问至少要分为多少个序列.且要保证排出来的子序列数最少. 思路: ( 9 , 4 ) ,( 2 , 5 ) ,( 1 ...

  8. POJ 1065 Wooden Sticks Greed&comma;DP

    排序后贪心或根据第二关键字找最长下降子序列 #pragma comment(linker, "/STACK:1024000000,1024000000") #include< ...

  9. POJ 1065 Wooden Sticks&num;贪心&plus;qsort用法

    (- ̄▽ ̄)-* 这道题用到了cstdlib库的qsort()函数: 用法链接:http://www.cnblogs.com/syxchina/archive/2010/07/29/2197382.h ...

随机推荐

  1. Python error&colon; Unable to find vcvarsall&period;bat

    在安装一些Python模块时,大部分是cpython写的模块时会发生如下错误 error: Unable to find vcvarsall.bat.先前的一篇文章:在Windows上安装Scrapy ...

  2. jquery back to top 页面底部的返回顶部按钮

    <!doctype html> <html lang="en"> <head> <meta charset="UTF-8&quo ...

  3. bootstrap-图文混排 media

    <!-- media 图文混排 media-left(right) 图片的区域 在左边显示(右边) media-body 内容区域 media-heading 内容区域里的标题 media-mi ...

  4. ACM Computer Factory

    ACM Computer Factory Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6104 Accepted: 2113 ...

  5. 【LEETCODE OJ】Copy List with Random Pointer

    Problem link: http://oj.leetcode.com/problems/copy-list-with-random-pointer/ Deepcopy a linked list ...

  6. poj 3295 Tautology

    点击打开链接 Tautology Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 8127   Accepted: 3115 ...

  7. hud 1241 Oil Deposits

    Oil Deposits Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Tot ...

  8. java&period;lang&period;ClassCastException&colon; sun&period;proxy&period;&dollar;Proxy11 cannot be cast to分析

    报这个错,只有一个原因,就是你转化的类型不对. 如果你的类是一个单实体类,也就是没有继承或是接口别的类. public class HjmServiceImpl {} 那么这样写就可以: HjmSer ...

  9. Freescale MKL16Z1288VF4 芯片调试接口

    WDOG监视内部系统操作,并在发生故障时强制复位.它可以运行在一个独立的1 kHz低功率振荡器,具有可编程刷新窗口,以检测程序流或系统频率的偏差. 看门狗计时器保持一个时间在系统上运行,并重置它,以防 ...

  10. 【笔记】Python基础四:迭代器和生成器

    一,迭代器协议和for循环工作机制 (一),迭代器协议 1,迭代器协议:对象必须提供一个next方法,执行该方法要么返回迭代中的下一项,要么就引起一个stopiteration异常,以终止迭代(只能往 ...