HDOJ.1051 Wooden Sticks (贪心)

Wooden Sticks

点我挑战题目

题意分析

给出T组数据,每组数据有n对数,分别代表每个木棍的长度l和重量w。第一个木棍加工需要1min的准备准备时间,对于刚刚经加工过的木棍,如果接下来的木棍l和w均小于等于上一根木棍的l和w那么就不许要准备时间,否则的话还需要1min的准备时间。求解对于每组数据,所需要的最小的准备时间是多少。

贪心策略。

对木棍进行降序排序,首要关键字是l,次要关键字是w(可以颠倒)。然后选取最顶端的木棍,向下遍历,对于当前木棍,若l和w均小于等于顶层木棍,那么标记它为已处理,并且更新此时木棍的数据,继续遍历,直到没有木棍未知。此时判断所有的木棍是否处理完,是的话输出结果,否则的话继续选取顶层没有处理的木棍,重复遍历的操作。

代码总览

/*
Title:HDOJ.1051
Author:pengwill
Date:2016-11-25
*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#define max 5005
using namespace std;
struct stick{
int len;
int weight;
bool fish;
}item[max];
bool cmp(stick a,stick b)
{
if(a.len == b.len){
return a.weight>b.weight;
}else{
return a.len>b.len;
}
} int main()
{
int t;
//freopen("in.txt","r",stdin);
scanf("%d",&t);
while(t--){
int n,i;
scanf("%d",&n);
for(i = 0;i<n;i++){
scanf("%d %d",&item[i].len,&item[i].weight);
}
sort(item,item+n,cmp);
int num = 0,nlen,nweight,cnt = 0,temp= 0;
while(num!= n){
for(i = temp;i<n;i++){
if(item[i].fish == false){
nlen = item[i].len;
nweight = item[i].weight;
item[i].fish = true;
num++;cnt++;i++;
temp = i;
break;
}
}
for(;i<n;i++){
if(item[i].fish == false && item[i].len<=nlen && item[i].weight<=nweight){
item[i].fish = true;
num++;
nlen = item[i].len;
nweight = item[i].weight;
}
}
}
printf("%d\n",cnt);
for(i = 0;i<n;i++){
item[i].fish = false;
} }
return 0;
//fclose(stdin);
}
上一篇:leetcode_222 Count Complete Tree Nodes


下一篇:easyui textarea回车导致datagrid 数据无法展示的问题