8980. 택배

https://www.acmicpc.net/problem/8980

8980번: 택배

 

 

티어 : 골드1

 

struct 구조체와 std sort를 활용해 택배가 도착하는 마을의 번호가 작은 배달 순서로, 도착 마을의 번호가 같다면 출발 마을의 번호가 큰 순서대로 정렬하였다.

 

정렬된 순서대로 배달을 진행하여 답을 구하였다.

 

#include<stdio.h>
#include<algorithm>

using namespace std;;

int n, c, m, ans;
int box[2005];

typedef struct{
    int s, e, cnt;
} transport;
transport arr[10005];

bool condition(transport &i, transport &j){
    if(i.e < j.e) return true;
    else if(i.e == j.e && i.s > j.s) return true;
    return false;
}

int main()
{
    scanf("%d %d", &n ,&c);
    scanf("%d", &m);

    for(int i=0 ; i<m ; i++) scanf("%d %d %d", &arr[i].s, &arr[i].e, &arr[i].cnt);
    sort(arr, arr+m, condition);

    for(int i=0 ; i<m ; i++){
        int findmax = 100000;
        for(int j=arr[i].s ; j<arr[i].e ; j++){
            findmax = min(findmax, min(box[j]+arr[i].cnt, c) - box[j]);
        }
        for(int j=arr[i].s ; j<arr[i].e ; j++){
            box[j] += findmax;
        }
        ans += findmax;
    }

    printf("%d", ans);
}