hoj Job!Job!Job!

3326 단어
hehe...
이것 은 아주 좋 은 문제 입 니 다. 다음은 두 가지 해법 을 제시 합 니 다. 사상 은 모두 욕심 을 사용 하지만 사용 하 는 데이터 구조 가 다 릅 니 다.
하나
#include<iostream>
using namespace std;

#define N 100000
struct Node {int t, v;} a[N];
int set[N+1];
int cmp(const Node &a, const Node &b){ return a.v > b.v;}

int main()
{
    int i,j,k;
    int n,m;
    while(scanf("%d %d", &n, &m) == 2)
    {
                    if(m > N) m = N;
                    for(i=0; i<n; i++)
                    {
                             scanf("%d %d", &a[i].t, &a[i].v);
                             if(a[i].t > m)  a[i].t = m;
                             }       
                                                              
                    sort(a, a+n, cmp);                    
                    for(i=0; i<=m; i++)
                    set[i] = i; 
                                      
                    int res = 0;
                    for(i=0; i<n; i++)
                    {
                             k = a[i].t;
                             while(k != set[k]) k = set[k];
                             if(k == 0) continue;
                             res += a[i].v;

                             int r = k - 1;
                             while(set[r] != r) r = set[r];
                             set[k] = r, set[a[i].t] = r;
                             }
                             printf("%d
", res); } return 0; }

2. STL 의 우선 순위 대기 열
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

#define N 100000
priority_queue <int> q;
struct Node{ int t, v;};
Node input[N+100];

int cmp(Node &a, Node &b)
{
    if(a.t < b.t)
    return 1;
    if(a.t == b.t && a.v < b.v)
    return 1;
    return 0;
    }

int main()
{
    int n ,m;
    while(scanf("%d %d", &n, &m) != EOF)
    {
                    while(!q.empty()) q.pop();
                    int i;
                    for(i=0; i<n; i++)
                    scanf("%d %d", &input[i].t, &input[i].v);
                    
                    //sort(input, input + n, cmp);
                    int t = m;
                    int res = 0;
                    int k = n-1;
                    while(t >= 1)
                    {
                               if(t <= input[k].t)
                               q.push(input[k].v), k--;
                               if(k == -1 || t > input[k].t)
                               {
                                    if(!q.empty())
                                    { 
                                       res += q.top();
                                       q.pop();
                                       //printf("####%d
", res); } t --; } } //if(!q.empty() && t == 1) res += q.top(); printf("%d
", res); } return 0; }

좋은 웹페이지 즐겨찾기