Uvalive 6424 - 러시아 인형 (욕심)

[제목 링크]: 여 기 를 클릭 하 세 요 ~ ~
[제목 부주의]:
모든 장난감 은 사용 할 수 있 는 공간 과 내부 에 수용 할 수 있 는 공간 이 있다.모든 장난감 은 하나의 장난감 만 직접 끼 워 넣 을 수 있 고 간접 적 으로 끼 워 넣 을 수 있다. 즉, A 세트 B, B 는 C 를 다시 끼 워 넣 을 수 있 지만 A 는 B 와 C 를 동시에 끼 워 넣 을 수 없다.A 가 B 를 채 울 수 있 는 조건 은 A 의 내부 공간 이 B 의 점용 공간 보다 엄 격 히 크다 는 것 이다.i 번 째 장난감 은 ci 를 사용 하 는 단위 가 있 는데 이 장난감 내부 에 남 은 공간 을 곱 하면 바로 비용 이다.적당 한 끼 워 넣 기 를 거 친 후 최소 비용 이 얼마 인지 물 어 봐 야 한다.
[사고]: 욕심 문제, 데이터 가 크 지 않 고 2 층 for 순환 판단 이 분명 하 며 매번 에 끼 워 넣 으 면 비용 이 줄어든다.모든 장난감 에 대해 서 는 다른 장난감 에 넣 으 려 면 조건 이 허락 되 는 상황 에서 단 위 를 찾 아 큰 세트 를 써 야 비용 이 줄 어 들 수 있다.단위 별 비용 은 큰 것 에서 작은 것 으로 정렬 되 며, 비용 이 같 을 때 내부 부 피 는 큰 것 에서 작은 것 으로 (ps: 실측 uvalive 부 피 는 작은 것 에서 큰 것 으로 도 맞습니다)
코드:

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,t;
struct node
{
    int out,in,c;
} p[N];
bool cmp(node a,node b)// sort the cost and volume
{
    if(a.c==b.c) return a.in>b.in;
    else  return a.c>b.c;
}
bool vis[N];
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(vis,false,sizeof(vis));
        int k,jj,sum,maxx=0;
        for(int i=1; i<=n; ++i)
        {
            scanf("%d%d%d",&p[i].out,&p[i].in,&p[i].c);
        }
        sort(p+1,p+n+1,cmp);
        sum=0;
        for(int i=1; i<=n; ++i)
        {
            int maxx=0;
            for(int j=1; j<=n; ++j)
            {
                if(i==j) continue;
                if(!vis[j]&&p[j].out<p[i].in)
                {
                    maxx=max(maxx,p[j].out);
                }
            }
            if(maxx!=0)
            {
                for(int j=1; j<=n; ++j)
                {
                    if(!vis[j]&&p[j].out==maxx)
                    {
                        vis[j]=true;
                        break;
                    }
                }
            }
            sum+=(p[i].in-maxx)*p[i].c;
        }
        cout<<sum<<endl;
    }
    return 0;
}

/*
3
5 4 1
4 2 2
3 2 1
7
after sort:
4 2 2  //         ，   =2*2=4
3 2 1  //         ，   =2*1=2
5 4 1  //      3     ，   =（4-3）*1=1；    =4+2+1=7
*/