列表

详情

NC244820. Card

描述

There are N cards on the table , the value of the i-th () card is a_i .

You need to perform the following operation exactly K times .

Choose a card i () , and change it's value to b_i . Please notice that you can not choose one card twice .

We prepared Q questions for you , each question is :

Firstly read M , and then read M integers id_1,id_2,...,id_M . If you can not choose cards id_1,id_2,...,id_M , what is the maximum sum of the card's values after you perform the operations above .

输入描述

There are two positive integers  in the first line .

The second line has N positive integers indicates  .

The third line has N positive integers indicates  .

Then an positive integer  in a new line .

Then Q line follows , each line begins with an integer  , then M integers indicates id_1,id_2,...,id_M (  if  ) .

Two adjacent integers in the same line are separated by a space .

The sum of M in Q queries is less than or equal to  .

输出描述

For each question , print an integer in one line indicates the answer .

示例1

输入: 

5 1
1 2 3 4 5
5 4 3 2 1
3
1 5
2 1 2
2 1 3

输出: 

19
15
17

原站题解

import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Python3 解法, 执行用时: 1933ms, 内存消耗: 42168K, 提交时间: 2022-10-22 15:53:29 

def main():

    n,k = map(int, input().split())

    nums = list(map(int , input().split()))

    numsd = list(map(int, input().split()))

    dd = []

    ssum = 0

    for i,a,b in zip(range(1,n+1) ,nums, numsd):

        dd.append((b-a,i ))

        ssum += a

    dd.sort(reverse=True)

    maxsum = 0

    kset = set()

    for i in range(k):

        maxsum += dd[i][0]

        kset.add(dd[i][1])

    t = int(input())

    for _ in range(t):

        que = map(int,input().split())

        cantused = set()

        for ii,nn in enumerate(que):

            if ii != 0:

                cantused.add(nn)

        tsum = maxsum

        ti = k

        for nn in cantused:

            if nn in kset:

                while dd[ti][1] in cantused:

                    ti+=1

                tsum -= numsd[nn-1]-nums[nn-1]

                tsum += dd[ti][0]

                ti+=1

        print(tsum+ssum)

main()

C++(g++ 7.5.0) 解法, 执行用时: 612ms, 内存消耗: 13812K, 提交时间: 2023-05-03 21:35:16 

#include<bits/stdc++.h>



#define int long long

using namespace std;

const int N=1e6+10; 

const int MOD=1e9+7;

int a[N],b[N],c[N],w[N],d[N];

vector<int>v;

bool cmp(int x,int y)

{

    return x>y;

}

signed main()

{

    int n,k;

    cin>>n>>k;

    int sum=0;

    for(int i=1;i<=n;++i)

    {

        cin>>a[i];

        sum+=a[i];

    } 

    for(int i=1;i<=n;++i)

    {

        cin>>b[i];

        c[i]=b[i]-a[i];

        w[i]=c[i];

    }

    sort(c+1,c+1+n,cmp);

    int p;

    for(int i=1;i<=k;++i)

    {

        sum+=c[i];

        p=c[i];

    }

    int q;

    cin>>q;

    while(q--)

    {

        int m,ans=sum;

        cin>>m;

        p=c[k];

        int l=k;

        for(int i=1;i<=m;++i)

        {

            int h;

            cin>>h;

            d[i]=w[h];

            

            

        }

        sort(d+1,d+1+m,cmp);

        for(int i=1;i<=m;++i)

        {

            if(d[i]>=p)

            {

                ans-=d[i];

                l++;

                ans+=c[l];

                p=c[l];

                

            }

            

        }

        cout<<ans<<'\n';

        

        

    }

    

    

    

    return 0;

}

C++(clang++ 11.0.1) 解法, 执行用时: 587ms, 内存消耗: 4668K, 提交时间: 2023-05-31 21:02:07 

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

typedef long long LL;

LL a[N];

LL b[N];

LL c[N];

LL d[N];

int n,m,k;

LL ans,sum;

int main(){

    cin>>n>>k;

    for(int i=1;i<=n;i++){

        cin>>a[i];

    }

    for(int i=1;i<=n;i++){

        cin>>b[i];

        c[i]=b[i]-a[i];

        sum+=a[i];

    }

    sort(c+1,c+n+1,greater<int>());

    for(int i=1;i<=k;i++){

//      if(c[i]>0) 

            sum+=c[i];

    }

    int q;

    cin>>q;

    while(q--){

        ans=sum;

        cin>>m;

        int x;

        for(int i=1;i<=m;i++){

            cin>>x;

            d[i]=b[x]-a[x];

        }

        sort(d+1,d+m+1,greater<int>());

        int i=1,j=k;

        while(d[i]>=c[j]&&i<=m){

            ans-=d[i];

            i++;

//          if(j<n){

                j++;

//              if(c[j]>0){

                    ans+=c[j];

//              }

//          }

        }

        cout<<ans<<endl;

    }

    return 0;

}

上一题

© 2025 nowcoder.com