hdu 4864(经典贪心+思维解决超时）

你的名字 2023-08-17 16:25 109阅读 0赞

题意：

给n个机器，m个任务。每个机器有运行时间和等级，每个任务执行时间和等级。

每个机器每天只能用一次，同时运行时间不能超过给定值。

能执行的任务的等级不能高于机器的等级。

执行一个任务能得到500\*x + 2 \* y的钱，求最多能得到多少钱。

思路：

首先从最难的任务去解决（对任务进行排序：时间高在前面，然后时间相同的情况下，等级高在前面----因为题中需要的是钱数多，我们看时间与等级的系数，可知先完成时间多的钱多）

我们从机器中时间达到Tesk\[i\].time  中找出等级最低达到Tesk\[i\].level ---如果每次我们都找机器时间和等级非常高，可能后面任务中存在等级很高的导致不能完成该任务    所以留最大剩余给后面----时间我们不用考虑，因为我们就是按时间去主排序的，主要是考虑level剩余

我写的超时错误代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    #define maxn 100008
    struct node{
        int time,level,flag;
    };
    node Tesk[maxn];
    node machine[maxn];
    
    int cmp(node a,node b)
    {
        if(a.time>b.time)
            return 1;
        else if(a.time<b.time)
            return 0;
        else
            return (a.level>b.level);
    }
    
    int main()
    {
        int N,M;
        while(~scanf("%d%d",&N,&M)){
        for(int i=0;i<N;i++)
        {
            scanf("%d%d",&machine[i].time,&machine[i].level);
            machine[i].flag=-1;
        }
        sort(machine,machine+N,cmp);
        for(int i=0;i<M;i++)
        {
            scanf("%d%d",&Tesk[i].time,&Tesk[i].level);
        }
        sort(Tesk,Tesk+M,cmp);
    
        long long sum=0;
        int x=0;
    
        for(int i=0;i<M;i++)  //对每个任务判断是否能完成
        {
            int j=0;
            while(j<N&&machine[j].time>=Tesk[i].time)  //找到时间最低匹配
                j++;
           // cout<<"machine[j].time"<<machine[j].time<<"machine[j].level:"<<machine[j].level<<endl;
    
            int mint=-1;
            for(int t=j-1;t>=0;t--)
            {
                if(machine[t].time<Tesk[i].time)
                    continue;
                if(machine[t].flag!=-1)
                    continue;
                if(mint==-1&&machine[t].level>=Tesk[i].level)
                mint=t;
                if(machine[t].level>=Tesk[i].level&&machine[mint].level>machine[t].level)
                mint=i;
            }
    
            if(mint!=-1){
            machine[mint].flag=1;
            sum+=(500*Tesk[i].time+2*Tesk[i].level);
            x++;
            }
        }
        printf("%d %lld\n",x,sum);
        }
    }

方法一：-------------------------二分降低时间复杂度

可以很明显地知道这是个贪心 但具体怎么贪心还是有点麻烦的。

先要将 任务按时间T进行 从大到小 如果T相同 则按难度从大到小排序。

机器则相反进行排序  将难度从小到大进行排序 如果难度相同则按T从小到大。

#include <iostream>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    typedef __int64 LL;
    LL n , m;
    LL cnt , ans;
    const int size = 100010;
    bool vis[size];
    struct data
    {
        int T , L;
        bool operator < ( const data& p ) const
        {
            if( T==p.T )
                return L > p.L;
            return T > p.T;
        }    
    }task[size];
    struct node
    {
        int T , L;
        bool operator < ( const node& p ) const
        {
            if( L==p.L )
                return T < p.T;
            return L < p.L;
        }
    }mach[size];
    
    void init( )
    {
        memset( vis , false , sizeof(vis) );
        cnt = ans = 0;
    }
    
    int find( int x )
    {
        int L = 0 , R = n , M;
        while( L<R )
        {
            M = ( L + R ) >> 1;
            if( mach[M].L>=x )
                R = M;
            else
                L = M + 1;
        }
        return L;
    }    
    
    void solve( )
    {
        int pos;
        for( int i = 0 ; i<m ; i++ )
        {
            pos = find( task[i].L );
            for( int j = pos ; j<n ; j++ )
            {
                if( !vis[j] && mach[j].T>=task[i].T )
                {
                    ++ cnt;
                    ans = ans + 1LL * 500 * task[i].T + 1LL * 2 * task[i].L;
                    vis[j] = true;
                    break;
                }
            }
        }
    }
    
    int main()
    {
        cin.sync_with_stdio(false);
        while( cin >> n >> m )
        {
            init( );
            for( int i = 0 ; i<n ; i++ ) //机器
            {
                cin >> mach[i].T >> mach[i].L;
            }
            for( int i = 0 ; i<m ; i++ ) //任务
            {
                cin >> task[i].T >> task[i].L;
            }
            sort( mach , mach+n );
            sort( task , task+m );
            solve( );
            cout << cnt << " " << ans << endl;
        }
        return 0;
    }

方法二：思维

### 思路: ###

贪心，按照先x后y的降序排列。

从大到小选择事件够的机器记录，

再每次从y往最大100来找第一个满足的机器执行某个任务。

#include <stdio.h>
    #include <algorithm>
    using namespace std;
    
    struct node1
    {
        int x;
        int y;
    }n1[100005],n2[100005];
    
    int cmp(node1 a,node1 b)
    {
        if(a.x != b.x)
           return a.x > b.x;
        else
            return a.y > b.y;
    }
    
    
    int main()
    {
        int i,j,k;
        int n,m;
        int cnt ;
        long long sum ;
    
        while(~scanf("%d%d",&n,&m))
        {
    
            for(i=0;i<n;i++)
            {
                scanf("%d%d",&n1[i].x,&n1[i].y);
            }
            for(i=0;i<m;i++)
            {
                scanf("%d%d",&n2[i].x,&n2[i].y);
            }
    
            sort(n1,n1+n,cmp);
            sort(n2,n2+m,cmp);
    
            int c[105] = {
        0};
            cnt =sum =0;
            for(i=0,j=0;i<m;i++)
            {
                while(j<n && n1[j].x >= n2[i].x)
                {
                    c[n1[j].y]++;
                    j++;
                }
    
                for(k=n2[i].y;k<100;k++)
                {
                    if(c[k])
                    {
                        c[k]--;
                        cnt++;
                        sum +=(n2[i].x*500 + n2[i].y*2);
                        break;
                    }
                }
            }
    
            printf("%d %lld\n",cnt,sum);
        }
    
    }

转载于:https://www.cnblogs.com/Aiahtwo/p/11339394.html