codeforces-#674-E

codeforces-#674-E

九月 30, 2020

E. Rock, Paper, Scissors

题意

AB两人玩n轮猜拳

A会出a1次石头a2次剪刀a3次布

A会出b1次石头b2次剪刀b3次布

问A的最小胜场和最大胜场

题解

最大胜场贪心求解 maxn=min(a[2],b[3])+min(a[1],b[2])+min(a[3],b[1]);

最小胜场可以将问题转化为最大流问题

也可以贪心考虑：结合下图和文字描述

首先需要知道A的最小胜场次数只会是A出1种拳时产生 不会存在A出布胜同时A出剪刀胜

就比如上图若B的S+P<A的P那么只能用B的R来填补A的P导致Awin

所以只需要分别求A出剪刀/石头/布取胜种最大的情况

minn=max({0,a[1]-b[3]-b[1],a[2]-b[2]-b[1],a[3]-b[3]-b[2]})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=3e5+5;
const ll Mod=998857459;

int main() {
    Turnoff;
    int n;cin>>n;
    int a[4],b[4];
    for(int i=1;i<4;i++)cin>>a[i];
    for(int i=1;i<4;i++)cin>>b[i];
    int maxn=min(a[1],b[2])+min(a[2],b[3])+min(a[3],b[1]);
    //cout<<maxn<<endl;
    int minn=max({0,a[1]-b[3]-b[1],a[2]-b[2]-b[1],a[3]-b[3]-b[2]});
    cout<<minn<<" "<<maxn<<endl;
}