CF1426E Rock, Paper, Scissors 题解

题目传送门:
Luogu:CF1426E Rock, Paper, Scissors
Codeforces:1426E

(打表找规律)
相信大家都会玩石头剪刀布,规则都已经知道了,那就不再赘述(话说Codforces题面打了一长串,看完结果发现是在跟我们解释怎么玩石头剪刀布)浪费光阴


蒟蒻瞟了一眼其他的题解,不是dfs就是跑网络流,慢的跟个乌龟一样
(O(1))没商量


最大值简单,就是让Alice能赢的尽量赢,于是有了(O(1))的柿子:(ans2 = min(a1,b2) + min(a2,b3) + min(a3,b1))


再说最小值:
我们先来手模一下样例:
样例1、2、3都太逊了
直接看样例4、5:
先看样例4:
(ans1 = 22)
(a1 = 479), (a2 = 178), (a3 = 29)
(b1 = 11) , (b2 = 145), (b3 = 530)
经过观察发现(ans1 = a2 - b1 - b2)
再看看样例5:
(ans1 = 119)
(a1 = 10) , (a2 = 53) , (a3 = 256)
(b1 = 182), (b2 = 103), (b3 = 34)
经过观察发现(ans1 = a3 - b2 - b3)
当时就猜想:ans1是不是一个有规律可循的数呢?
猜想完后立刻将第三种情况也推了出来:
(ans1 = a1 - b3 - b1)
于是我们就有了成功的(O(1))算法
最小值代码片段:

if(min(a1, b2) > min(a2, b3) && min(a1, b2) > min(a3, b1))
  ans1 = a1 - b1 - b3;
else
  if(min(a2, b3) > min(a1, b2) && min(a2, b3) > min(a3, b1))
    ans1 = a2 - b2 - b1;
  else
    if(min(a3, b1) > min(a1, b2) && min(a3, b1) > min(a2, b3))
      ans1 = a3 - b3 - b2;
    else
      ans1 = 0;

最后放出完整的代码:

#include<bits/stdc++.h>
using namespace std;
int n, a1, a2, a3, b1, b2, b3, ans1, ans2;
int main() {
	scanf("%d", &n);
	scanf("%d%d%d", &a1, &a2, &a3);
	scanf("%d%d%d", &b1, &b2, &b3);
	if(min(a1, b2) > min(a2, b3) && min(a1, b2) > min(a3, b1))
		ans1 = a1 - b1 - b3;
	else
		if(min(a2, b3) > min(a1, b2) && min(a2, b3) > min(a3, b1))
			ans1 = a2 - b2 - b1;
		else
			if(min(a3, b1) > min(a1, b2) && min(a3, b1) > min(a2, b3))
				ans1 = a3 - b3 - b2;
			else
				ans1 = 0;
	ans2 = min(a1, b2) + min(a2, b3) + min(a3, b1);
	printf("%d %d", max(ans1, 0), ans2);
	return 0;
}

话说就不能顺手点个推荐吗?
最后zc一下自己的blog:
博客园
洛谷

原文地址:https://www.cnblogs.com/Wuzhuoming-sirenboke/p/13752145.html