hoj Job!Job!Job!
이것 은 아주 좋 은 문제 입 니 다. 다음은 두 가지 해법 을 제시 합 니 다. 사상 은 모두 욕심 을 사용 하지만 사용 하 는 데이터 구조 가 다 릅 니 다.
하나
#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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.