欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}

 

相关标签: 贪心