Codeforces Round #674 (Div. 3) E. Rock, Paper, Scissors
题目链接
Alice and Bob have decided to play the game “Rock, Paper, Scissors”.
The game consists of several rounds, each round is independent of each other. In each round, both players show one of the following things at the same time: rock, paper or scissors. If both players showed the same things then the round outcome is a draw. Otherwise, the following rules applied:
if one player showed rock and the other one showed scissors, then the player who showed rock is considered the winner and the other one is considered the loser;
if one player showed scissors and the other one showed paper, then the player who showed scissors is considered the winner and the other one is considered the loser;
if one player showed paper and the other one showed rock, then the player who showed paper is considered the winner and the other one is considered the loser.
Alice and Bob decided to play exactly n rounds of the game described above. Alice decided to show rock a1 times, show scissors a2 times and show paper a3 times. Bob decided to show rock b1 times, show scissors b2 times and show paper b3 times. Though, both Alice and Bob did not choose the sequence in which they show things. It is guaranteed that a1+a2+a3=n and b1+b2+b3=n.
Your task is to find two numbers:
the minimum number of round Alice can win;
the maximum number of rounds Alice can win.
Input
The first line of the input contains one integer n (1≤n≤1e9) — the number of rounds.
The second line of the input contains three integers a1,a2,a3 (0≤ai≤n) — the number of times Alice will show rock, scissors and paper, respectively. It is guaranteed that a1+a2+a3=n.
The third line of the input contains three integers b1,b2,b3 (0≤bj≤n) — the number of times Bob will show rock, scissors and paper, respectively. It is guaranteed that b1+b2+b3=n.
Output
Print two integers: the minimum and the maximum number of rounds Alice can win.
Examples
input
2
0 1 1
1 1 0
output
0 1
input
15
5 5 5
5 5 5
output
0 15
input
3
0 0 3
3 0 0
output
3 3
input
686
479 178 29
11 145 530
output
22 334
input
319
10 53 256
182 103 34
output
119 226
思维题~
比赛时真的想不到怎么做最优，看了题解恍然大悟/(ㄒoㄒ)/~~
首先求最多的场数很简单，就是每一种出法能赢的最大场数加起来即可，难点就在于求最小，不难发现，有 666 种输的情况，333 种平局，333 种输，很显然最优解就在于 666 种情况的排列，所以直接求一个全排列即可，AC代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>a,b;
int n,x;
int main(){
cin>>n;int ans=n;for(int i=0;i<3;i++) cin>>x,a.push_back(x);for(int i=0;i<3;i++) cin>>x,b.push_back(x);vector<pair<int,int>>v;v.push_back({
0,0});v.push_back({
1,1});v.push_back({
2,2});v.push_back({
0,2});v.push_back({
1,0});v.push_back({
2,1});sort(v.begin(),v.end());do{
vector<int>a1=a,b1=b;for(auto u:v){
a1[u.first]-=min(a1[u.first],b1[u.second]);b1[u.second]-=min(a1[u.first],b1[u.second]);}ans=min(ans,min(a1[0],b1[1])+min(a1[1],b1[2])+min(a1[2],b1[0]));}while(next_permutation(v.begin(),v.end()));cout<<ans<<" "<<min(a[0],b[1])+min(a[1],b[2])+min(a[2],b[0]);return 0;
}