2021 가을 순풍 8.20 필기시험 모집

서버: 작은 A는 n개의 서버가 있고 i번째 서버는ai의 대역폭을 가지고 있습니다.m명의 고객이 서버를 임대하는데 i번째 고객은 적어도 대역폭이 bi인 서버를 필요로 하고ci원을 예산으로 쓰기를 원한다.(빌려줄 수 없으면 0), 작은 A는 일부 사람을 거절할 수 있습니다. 지금 작은 A의 서버에 최대 얼마를 그룹화할 수 있습니까?입력: 341, 2, 3, 2, 1, 3, 2, 3, 1, 출력: 5 사고방식: 임대료 욕심을 참조하면 되고, 임대료가 같으면 대역폭 수요가 적은 고객에게 우선 임대한다.코드:

#include
using namespace std;
// ， ； ， ( )
bool cmp(const pair<int,int>& a,const pair<int,int>& b){
    if(a.second == b.second){
        return a.first < b.first;
    }
    else if(a.second < b.second){
        return false;
    }
    else{
        return true;
    }
}
int main(){
    int n,m;
    while (cin >> n >> m){
        vector<int> bandwide(n,0);
        vector<pair<int,int>> guests(m,make_pair(0,0));
        for (int i = 0; i < n; ++i) {
            cin >>bandwide[i];
        }
        for (int i = 0; i < m; ++i) {
            cin >>guests[i].first>>guests[i].second;
        }
        // 
        sort(bandwide.begin(),bandwide.end());
        sort(guests.begin(),guests.end(),cmp);
        int maxval = 0;
        for (int i = 0; i < m; ++i) {
            // lower_bound ， >=val 
            auto it = lower_bound(bandwide.begin(),bandwide.end(),guests[i].first);
            // 
            if(it != bandwide.end()){
                maxval += guests[i].second;
                bandwide.erase(it);
            }
        }
        cout<< maxval<<endl;
    }
}

상금: n개의 퀘스트가 있습니다. 모든 퀘스트는 l, r, w로 퀘스트 시작, 종료 시간, 그리고 얻을 수 있는 돈을 표시합니다.크리스는 임무가 충돌하지 않는 상황에서 최대 얼마의 돈을 얻을 수 있는 욕심쟁이였다.입력: 3 1 3 5 2 7 3 5 10 1 출력: 6 사고방식: 동적 기획 상태 정의: dp[i]는 전 i+1 임무가 얻을 수 있는 최대 수익을 나타낸다.이동 방정식: i+1 작업은 이전 IndexCanPut(i) 작업 뒤에 연결할 수 있습니다: dp[i] = max(dp[i-1], dp[IndexCanPut(i)] + arr[i].money) 제1항 퀘스트는 앞의 퀘스트 뒤에 연결할 수 없습니다: dp[i]=max(dp[i-1],arr[i].money) 코드:

#include
using namespace std;

struct task{
    int l,r,money;
};

typedef vector<task> task_arr;

int IndexCanPut(task_arr& arr,int i){
    for (int j = i-1; j >= 0 ; --j) {
        if(arr[j].r <= arr[i].l)
            return j;
    }
    return -1;
}
bool cmp(task a,task b){
    return a.r < b.r;
}

int task_sort(task_arr &arr){
    int N = arr.size();
    sort(begin(arr),end(arr),cmp);
    vector<int> dp(N);
    dp[0] = arr[0].money;
    for (int i = 1; i < N; ++i) {
        int inc_profit = arr[i].money;
        int l =IndexCanPut(arr,i);
        if(l != -1){
            inc_profit +=dp[l];
        }
        dp[i] = max(inc_profit,dp[i-1]);
    }
    return dp[N-1];
}
int main(){
    int n;
    while (cin >> n){// 
        vector<task> tasks(n);
        for (int i = 0; i < n; ++i) {
            task temp;
            int temp1,temp2,temp3;
            cin >> temp1>>temp2>> temp3;
            temp.l = temp1;
            temp.r = temp2;
            temp.money = temp3;
            tasks[i] = temp;
        }
        cout<< task_sort(tasks)<<endl;
    }
}