POJ-1065 Wooden Sticks 【贪心+标记】
程序员文章站
2024-03-13 23:09:04
...
题目:给你 N 个木棍,每根木棍都有一个长度 l 和一定重量 w 。机器每对一根进行操作需要一分钟的时间 ,但是如果当前进行操作的木棍的长度和重量都不小于前一根,那么这根木棍就不需要加时间。
题解:贪心+标记。
先按照长度由小到大排序,如果长度一样,则按照重量由小到大排序。依次操作每根木棍,同时标记已经操作。
操作当前木棍时,同时检查是否可以使它后面的木棍直接操作而且不用加时间,如果可以,则直接操作并且标记已操作,同时更新操作的木棍的重量。
AC代码:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define io ios::sync_with_stdio(0),cin.tie(0)
#define ms(arr) memset(arr,0,sizeof(arr))
#define inf 0x3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+7;
struct node
{
int l;
int w;
}a[maxn];
bool cmp(node a,node b)
{
if(a.l==b.l)
return a.w<b.w;
return a.l<b.l;
}
int t,n;
bool vis[maxn];
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].l>>a[i].w;
vis[i]=false;
}
sort(a+1,a+1+n,cmp);
int ans=0;
for(int i=1;i<=n;i++)
{
if(vis[i])//检查该木棍是否已经被操作
continue;
ans++;//操作数+1
int weight=a[i].w;//维护当前操作的重量
for(int j=i+1;j<=n;j++)
{
if(!vis[j]&&a[j].w>=weight)//若木棍的重量不小于当前操作的重量,则该木棍可被操作
{
weight=a[j].w;//更新当前操作的木棍的重量
vis[j]=true;//同时标记已操作
}
}
}
cout<<ans<<endl;
}
return 0;
}
上一篇: Linux服务器搭建之Apache和Tomcat的搭建
下一篇: 备忘:我常用的pandas操作