E. Rock, Paper, Scissors
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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 nn rounds of the game described above. Alice decided to show rock a1a1 times, show scissors a2a2 times and show paper a3a3 times. Bob decided to show rock b1b1 times, show scissors b2b2 times and show paper b3b3 times. Though, both Alice and Bob did not choose the sequence in which they show things. It is guaranteed that a1+a2+a3=na1+a2+a3=n and b1+b2+b3=nb1+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 nn (1≤n≤1091≤n≤109) — the number of rounds.
The second line of the input contains three integers a1,a2,a3a1,a2,a3 (0≤ai≤n0≤ai≤n) — the number of times Alice will show rock, scissors and paper, respectively. It is guaranteed that a1+a2+a3=na1+a2+a3=n.
The third line of the input contains three integers b1,b2,b3b1,b2,b3 (0≤bj≤n0≤bj≤n) — the number of times Bob will show rock, scissors and paper, respectively. It is guaranteed that b1+b2+b3=nb1+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
Note
In the first example, Alice will not win any rounds if she shows scissors and then paper and Bob shows rock and then scissors. In the best outcome, Alice will win one round if she shows paper and then scissors, and Bob shows rock and then scissors.
In the second example, Alice will not win any rounds if Bob shows the same things as Alice each round.
In the third example, Alice always shows paper and Bob always shows rock so Alice will win all three rounds anyway.
題意：
alice和bob玩剪刀石頭布，已知alice出了a1個石頭、a2個剪刀、a3個步，bob出了b1個石頭、b2個剪刀、b3個布，問alice最少贏了多少次，最多贏了多少次，
思路：
1、最多贏多少次
讓alice盡量贏就可以了 maxx = min(a1, b2) + min(a2, b3) + min(a3, b1);
2、最少贏多少次
考慮讓alice盡量輸或平，也就是讓a1和b1、b3更多地抵消掉，a2和b2、b1更多地抵消掉，a3和b3、b2更多地抵消掉，抵消后，最優的最終狀態肯定是（全為0）或者（alice剩下一種且bob剩下一種），全為0就不用說了，剩下的情況肯定都是alice贏（因為抵消的都是對贏沒有貢獻的，無法抵消肯定是有貢獻，也就是alice贏），
還有一個小問題，alice如果有剩余一定是一種嗎，答案是肯定的，因為如果alice剩下了兩種：a2個剪刀和a3個布，bob剩下了一種：b1個石頭，（a2 + a3 == b1就不用解釋了8）此時還可以讓alice的剪刀和石頭相抵消，也就是某人剩下兩種時根本不是最終狀態，還可以繼續抵消，因此有剩余情況下的最終狀態肯定是每人一種，
下面來討論一下抵消后alice有剩余的情況：
（1）如果剩下a1，那對應剩下的就是b2，a1 == b2，
整個程序讓b2盡量消失，所以a1、b2的剩余量均為 b2 - a2 - a3，（這里也可以考慮成讓a1盡量地消失，a1、b2的剩余量為a1 - b1 - b3）
（2）如果剩下a2，那對應剩下的就是b3，a2 == b3，
整個程序讓b3盡量消失，所以a2、b3的剩余量均為 b3 - a1 - a3，（這里也可以考慮成讓a2盡量地消失，a2、b3的剩余量為a2 - b1 - b2）
（3）如果剩下a3，那對應剩下的就是b1，a3 == b1，
整個程序讓b1盡量消失，所以a3、b1的剩余量均為 b1 - a1 - a2，（這里也可以考慮成讓a3盡量地消失，a3、b1的剩余量為a3 - b2 - b3）
現在來看一下這三個數（b2 - a2 - a3）、（b3 - a1 - a3）、（b1 - a1 - a2）這三個數中最多只有一個正數，證明如下：
假設 b2 - a2 - a3 > 0，即 b2 > a2 + a3
因為 b1 + b2 + b3 == a1 + a2 + a3 == n
所以 b1 + b3 < a1
所以 b1 < a1 + a2 且 b3 < a1 + a3
所以上面三個數中最多只有一個正數，
所以最終的答案就是從（b2 - a2 - a3）、（b3 - a1 - a3）、（b1 - a1 - a2）中選一個最大值就可以了，
如果上面考慮讓a1、a2、a3盡量地消失就是從（a1 - b1 - b3）、（a2 - b1 - b2）、（a3 - b2 - b3）中選一個最大值，答案是一樣的，因為alice和bob剩下的數肯定相同，
碼 字 好 累 啊
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 10;
const int M = 1e5 + 10;
int main() {
int n, a[4], b[4];
scanf("%d", &n);
for(int i = 1; i <= 3; ++i) scanf("%d", &a[i]);
for(int i = 1; i <= 3; ++i) scanf("%d", &b[i]);
///surprise max居然可以加大括號
int minn = max({0, a[1] - b[1] - b[3], a[2] - b[2] - b[1], a[3] - b[3] - b[2]});
int maxx = min(a[1], b[2]) + min(a[2], b[3]) + min(a[3], b[1]);
printf("%d %d\n", minn, maxx);
return 0;
}
最小費用最大流：
超級源點向alice的石頭、剪刀、布連邊，流量分別為a1、a2、a3，費用都為0
bob的石頭、剪刀、布連邊，流量分別為b1、b2、b3，費用都是0
alice的三種決策向bob的三種決策連邊，流量都為inf，只有alice贏時費用為1（貢獻一個贏）
套板子就完了
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define P pair<int,int>
const int inf = 0x3f3f3f3f;
const int N = 1e4 + 10;
const int M = 1e5 + 10;
struct node {
int x, y;
};
vector<node>peo, house;
struct Edge {
int to, cap, cost, rev;
};
int n, m, s, t;
int u, v, c, w;
int maxFlow, minCost;
vector<Edge> G[N];
int h[N]; ///頂點的勢
int dist[N], prevv[N], preve[N]; ///dist最短距離 prevv最短路中的父節點 preve最短路中的父邊
void init() {
maxFlow = 0;
minCost = 0;
for(int i = 0; i < N; ++i)
G[i].clear();
}
void addedge(int from, int to, int cap, int cost) {
Edge temp1 = { to, cap, cost, (int)G[to].size() };
Edge temp2 = { from, 0, -cost, (int)G[from].size() - 1 };
G[from].push_back(temp1);
G[to].push_back(temp2);
}
void MCMF(int s, int t, int f, int n) { //n是總結點數
fill(h + 1, h + 1 + n, 0);
while (f > 0) {
priority_queue<P, vector<P>, greater<P> > D;
memset(dist, inf, sizeof(dist));
dist[s] = 0; D.push(P(0, s));
while (!D.empty()) {
P now = D.top(); D.pop();
if (dist[now.second] < now.first) continue;
int v = now.second;
for (int i = 0; i<(int)G[v].size(); ++i) {
Edge &e = G[v][i];
if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
D.push(P(dist[e.to], e.to));
}
}
}
if (dist[t] == inf) break;
for (int i = 1; i <= n; ++i) h[i] += dist[i];
int d = f;
for (int v = t; v != s; v = prevv[v])
d = min(d, G[prevv[v]][preve[v]].cap);
f -= d; maxFlow += d;
minCost += d * h[t];
for (int v = t; v != s; v = prevv[v]) {
Edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
}
int main() {
int cnt, a[4], b[4];
while(~scanf("%d", &cnt)) {
init();
n = 8, s = 0, t = 7;
for(int i = 1; i <= 3; ++i) {
scanf("%d", &a[i]);
addedge(s, i, a[i], 0);
}
for(int i = 1; i <= 3; ++i) {
scanf("%d", &b[i]);
addedge(i + 3, t, b[i], 0);
}
int maxx = min(a[1], b[2]) + min(a[2], b[3]) + min(a[3], b[1]);
for(int i = 1; i <= 3; ++i) {
for(int j = 1; j <= 3; ++j) {
int cst = 0;
if(i == 1 && j == 2) cst = 1;
if(i == 2 && j == 3) cst = 1;
if(i == 3 && j == 1) cst = 1;
addedge(i, j + 3, inf, cst);
}
}
MCMF(s, t, inf, n + m + 2);
printf("%d %d\n", minCost, maxx);
}
return 0;
}
/*
2
0 1 1
1 1 0
15
5 5 5
5 5 5
3
0 0 3
3 0 0
686
479 178 29
11 145 530
319
10 53 256
182 103 34
94317
66277 24448 3592
3499 24653 66165
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/143158.html
標籤：其他