hdu 4864 작업(욕심)

제목:http://acm.hdu.edu.cn/showproblem.php?pid=4864
n 대의 기계,m 개의 임무,모든 기계 와 임 무 는 두 개의 값 이 있 습 니 다.기계 의 두 개의 값 time,level 이 모두 임무 time 보다 크 거나 같 을 때 이 기 계 는 이 임 무 를 완성 할 수 있 습 니 다.모든 기 계 는 하나의 임 무 를 완성 할 수 있 고 하나의 임 무 를 완성 하면 5*time+2*level 을 증가 할 수 있 습 니 다.가장 큰 임 무 를 완성 하 는 양 을 물 어보 고 완 성 량 이 같 으 면 가장 큰 결과 치 를 구 할 수 있 습 니 다.
주로 시간 에 따라 큰 것 부터 작은 것 까지 정렬 합 니 다.(그 영향 이 크기 때 문 입 니 다)시간 이 같 을 때 level 크기 를 참조 하여 정렬 하고 큰 것 부터 작은 것 까지 정렬 합 니 다.그리고 한 기계 와 미 션 PK 를 하나씩 하 세 요.그런데 이렇게 하 는 것 은 잘못된 것 입 니 다.
4.567913.나중에 인터넷 에서 검색 해 보 니 모든 task 에 대해 선 결 조건(time)의 최소 level 값 을 만족 시 키 는 기 계 를 선택해 야 한 다 는 것 을 알 게 되 었 다.

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e5+10;
struct node{
    int time,level;
}ma[maxn],ta[maxn];
bool cmp(node a,node b){
    if(a.time>b.time)return 1;
    if(a.time==b.time&&a.level>b.level)return 1;
    return 0;
}
int main()
{
    //freopen("cin.txt","r",stdin);
    int n,m;
    while(cin>>n>>m){
        memset(ma,0,sizeof(ma));
        memset(ta,0,sizeof(ta));
        int i,j;
        for(i=0;i<n;i++)scanf("%d%d",&ma[i].time,&ma[i].level);
        for(i=0;i<m;i++)scanf("%d%d",&ta[i].time,&ta[i].level);
        sort(ma,ma+n,cmp);
        sort(ta,ta+m,cmp);
        i=0;   j=0;
        long long cnt=0,sum=0;
        while(i<n&&j<m){  //      
            if(ma[i].time>=ta[j].time&&ma[i].level>=ta[j].level){
                sum+=(500*ta[j].time+2*ta[j].level);
                i++;
                cnt++;
            }
            j++;
        }
        printf("%lld %lld
",cnt,sum);
    }
    return 0;
}

중간의 코드 구상 이 정말 교묘 하 다.처음에 누가 먼저 생각 했 는 지 모르겠다.이런 생각 은 확실히 더욱 엄밀 하 다 고 느 꼈 지만,사실 나 는 원래 의 생각 에 대해 여전히 무엇이 잘못 되 었 는 지 모른다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[HDU] 4089 활성화 확률 DP

dp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

hdu 4864 작업(욕심)

좋은 웹페이지 즐겨찾기