hdu 4864 Task【欲張り】

3808 ワード

Task
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5241 Accepted Submission(s): 1365
Problem Description
Today the company has m tasks to complete. The ith task need xi minutes to complete. Meanwhile, this task has a difficulty level yi. The machine whose level below this task’s level yi cannot complete this task. If the company completes this task, they will get (500*xi+2*yi) dollars.
The company has n machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.
The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.

Input
The input contains several test cases.
The first line contains two integers N and M. N is the number of the machines.M is the number of tasks(1 < =N <= 100000,1<=M<=100000).
The following N lines each contains two integers xi(0The following M lines each contains two integers xi(0
Output
For each test case, output two integers, the maximum number of the tasks which the company can complete today and the money they will get.

Sample Input

Sample Output

n個の機械があってm個の任務があって、機械xとyがすべて任務のxより大きいことを必要として、yは500*x+2*yの任務の報酬を得ることができて、最大でどれだけの任務を解決することができて、全部でどれだけの報酬を得ることができます.
解題の構想:タスクのxを並べ替えて、機械のxを並べ替えて、それからfor一回のタスク、機械の中で条件に合致するxj>=xiを探します.次に,条件を満たすすべてのxjにおいて,yjが最小であることを,このタスクを解決する機械として見つけた.
ACコード:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
struct task
{
    int x,y;
    friend bool operator <(task a,task b)
    {
        return a.y<b.y;
    }
}a[100005],b[100005];
int vis[120];
int cmp(task a,task b)
{
    if(a.x!=b.x)return a.x>b.x;
    else return a.y>b.y;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&b[i].x,&b[i].y);
        }
        sort(a,a+n,cmp);
        sort(b,b+m,cmp);
        memset(vis,0,sizeof(vis));
        int j=0;
        int cont=0;
        __int64 output=0;
        for(int i=0;i<m;i++)
        {
            while(j<n&&a[j].x>=b[i].x)
            {
                vis[a[j].y]++;
                j++;
            }
            for(int k=b[i].y;k<=100;k++)
            {
                if(vis[k]>0)
                {
                    cont++;
                    vis[k]--;
                    output+=500*b[i].x+2*b[i].y;
                    break;
                }
            }
        }
        printf("%d %I64d
",cont,output);
    }
}

transformersのBertJapaneseTokenizerでMeCabオプション

JAva CSVファイルの操作