手机买球

hiho一下第316周《小Hi与钢铁侠》题目分析

1
0

本题是一道贪心题目

首先计算出 没有JARVIS支持时,每种插槽(Ci个)应该安装哪些模块,可以使总威力最大。

显然每种插槽按威力从大到小选Ci个即可。(注意只从无需JARVIS支持的模块中选)

其次,考虑K个JARVIS支持"点数",应该分配给哪些插槽。

手机买球这一步也是贪心,我们只要每次都分配给“收益最大”的插槽即可。

如果我们分配给第i种插槽,那么提升就是第i种插槽尚未安装的模块中威力最大的 减去 第i种插槽已经安装的模块中威力最小的。于是遍历所有插槽种类,从中选收益最大的即可。

以上是基本的贪心思路,不过实际要考虑很多边界情况。比如模块数量不足、有JARVIS的模块威力反而不如没有JARVIS的模块等等。

1 answer(s)

0

include

include

include

include

using namespace std;

define maxn2 10005

define min(a,b) (a>b)? b:a

define max(a,b) (a>b)? a:b

int TT; int N,M,K;//N个武器 M个插槽 K个jarvis支持

手机买球int vectorSize(vector V,int n){ int sum = 0; for(int i = 0;i

bool cmp(int x1, int x2){ return x1>x2; }

手机买球struct Node{ vector T0;//储存 vector T1;//储存 }; vector P;

int C[maxn2]; int pre_cnt[maxn2];//第i个武器插槽不使用JARVIS支持的威力

手机买球int main (){ scanf("%d",&TT); while(TT--){

    scanf("%d%d%d",&N,&M,&K);//N个武器 M个武器插槽 K个jarvis支持

    P.resize(M+1);//

    for(int i = 0;i<=M;i++) P.clear();

    for(int i = 0;i<N;i++)
    {
        int temp_vv,temp_pp,temp_tt;
        scanf("%d%d%d",&temp_vv,&temp_pp,&temp_tt);
        if(temp_tt == 0) P[temp_pp].T0.push_back(temp_vv);//最好是把T0补0至Ci一样多 这样少了很多处理的判断
        if(temp_tt == 1) P[temp_pp].T1.push_back(temp_vv);

    }

    for(int i = 1; i <= M; i++){
        scanf("%d",&C[i]);
    }

    //若T0<Ci
    //最好是把T0补0至Ci一样多 这样少了很多处理的判断
    //判断有:直接加上T1的第一个字母或者是替换。
    for(int i = 0;i <= M; i++){
        int T0_size = P[i].T0.size();
        for(int j = 0; j<C[i]-T0_size; j++) P[i].T0.push_back(0);
    }


    for(int i = 1; i<=M;i++){
        sort(P[i].T0.begin(),P[i].T0.end(),cmp);
        sort(P[i].T1.begin(),P[i].T1.end(),cmp);

// for(int j = 0;j

    vector<int> Profit;
    Profit.clear();


    for(int i = 1; i<=M;i++){//第i个武器插槽
        int size_0 = P[i].T0.size();//不需要JARVIS支持的武器个数
        int size_1 = P[i].T1.size();//需要JARVIS支持支持的武器的个数

        pre_cnt[i] = vectorSize(P[i].T0,C[i]);;//第i个武器插槽不使用JARVIS支持的总威力

        //开始替换
        for(int j = 0;j<size_1;j++){
            if((C[i]-j-1 >= 0)&&P[i].T1[j] - P[i].T0[C[i]-j-1] > 0) Profit.push_back(P[i].T1[j] - P[i].T0[C[i]-j-1]);
        }
    }

    int Profit_sum = 0;

    //取前K个正的Profit作为利息的总值。
    //for(int i = 0;i<Profit.size();i++) printf("%d \n",Profit[i]);

    sort(Profit.begin(),Profit.end(),cmp);

    K = min(Profit.size(),K);

    for(int i = 0; i < K; i++) Profit_sum+=Profit[i];

    for(int i = 1; i <= M; i++) Profit_sum+=pre_cnt[i];

    printf("%d\n",Profit_sum);
}

}

write answer 切换为英文 切换为中文


转发分享

bet366线上买球188bet手机版客户端bet820bet36在线开户