GPAInvolution

NC216210. GPAInvolution

描述

众所周知 $Hile{}$ 老师喜欢口嗨和上课抽人回答问题。它问的问题只有两个选项，不管你选哪个都会被他口头扣分。但是由于 $Hile{}$ 老师不想让学生挂科，所以期末时他的扣分算法会改为：
你所选的 $A{}$ 选项中扣分最多的一个分 + 你所选的 $B{}$ 选项中扣分最多的一个分。
$Boboge{}$ 是个卷绩点人，他希望扣最少的分来让总评尽可能高。已知他该学期被问了 $n{}$ 个问题，给你每个问题的 $A{}$ 选项扣的分和 $B{}$ 选项扣的分，请你求出他最少可以只扣几分。
TL, DR;用数学语言复读一遍:

有 $n{}$ 个对数，对于每对数 $(a_i,b_i)$ ，可以将 $a_i$ 加入集合 $A{}$ 或将 $b_i$ 加入集合 $B{}$ ，每对数能且只能选择一个元素加入对应集合，请你选择一个方案使得 $max(B) + max(A){}$ 最小，规定 $max( \varnothing ) = 0$ 。（ $\varnothing{}$ 代表空集合，即集合中一个元素都没有。）

输入描述

第一行输入一个数 ，表示有  道题目。
第二行输入  个数 ，表示每道题目选选项扣的分。
第三行输入  个数 ，表示每道题目选选项扣的分。

输出描述

输出一个数，表示题面所说的最小值。

示例1

输入:

5
1 2 3 4 5
5 4 3 2 1

输出:

说明:

对于样例，前三道题选 $A{}$ ，后两道题选 $B{}$ ， $max(A)=3,max(B)=2{}$ 。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 274ms, 内存消耗: 15096K, 提交时间: 2020-12-31 01:07:30

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<vector<int>> v(n,vector<int>(2));
    for(int i=0;i<n;i++)cin>>v[i][0];
    for(int i=0;i<n;i++)cin>>v[i][1];
    sort(v.begin(),v.end());
    int da=0;
    int res=INT_MAX;
    for(int i=n-1;i>=0;i--){
        res=min(res,v[i][0]+da);
        da=max(da,v[i][1]);
    }
    res=min(res,da);
    cout<<res;
	return 0;
}

Python3(3.9) 解法, 执行用时: 459ms, 内存消耗: 59256K, 提交时间: 2020-12-26 18:34:33

n,z,ans,t=input(), list(zip(map(int,input().split()),map(int,input().split()))),1e10,0
for a,b in sorted(z)[::-1]:
    ans,t= min(ans,a+t),max(t,b)
print(min(ans,t))

上一题

下一题

详情