题解 CF1366A 【Shovels and Swords】

题意:

给你 (a) 个木棍, (b) 钻石。

你可以制作 (2) 种武器:

  • 铲子:由 (2) 个木棍和 (1) 个钻石组成。

  • 剑:由 (1) 个木棍和 (2) 个钻石组成。

每种武器都可以出售 (1) 个祖母绿。

问你最多可以得到多少祖母绿。


应该很简单吧。

(a)(b) 可以以任何比例 (小于 (1) : (2)) 相配

这里证明一下:

对于一个数 (x)(3) 的倍数。令其为 (3 * y <= 3 * min(a, b))

那么必然可以分为 (m)(a)(2 * b)(n)(a * 2)(b) 相关。

感性理解下(很好理解

所以只需要判断一下

max(a, b) > min(a, b) * 2

具体代码如下:

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#define N 2000
#define M 8000010
#define ls x << 1
#define rs x << 1 | 1
#define inf 0x3f3f3f
#define inc(i) (++ (i))
#define dec(i) (-- (i))
#define mid ((l + r) >> 1)
// #define int unsigned __int128
//#define ll long long
#define XRZ 19260817
#define pai acos(-1)
#define debug() puts("XRZ TXDY");
#define mem(i, x) memset(i, x, sizeof(i));
#define Next(i, u) for(register int i = head[u]; i ; i = e[i].nxt)
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout);
#define Rep(i, a, b) for(register int i = (a) , i##Limit = (b) ; i <= i##Limit ; inc(i))
#define Dep(i, a, b) for(register int i = (a) , i##Limit = (b) ; i >= i##Limit ; dec(i))
using namespace std;
inline int read() {
    register int x = 0, f = 1; register char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c 	- 48, c = getchar(); 
    return x * f;
}
inline int read_plus() {
    register int res = 0, ch = getchar();
    while(!isdigit(ch) and ch != EOF) ch = getchar();
    while(isdigit(ch)) res = ((res << 3) + (res << 1) + (ch - '0')) % XRZ, ch = getchar();
    return res;
}	
int dx[10] = {0, 1, 1, 2, 2, -1, -1, -2, -2};
int dy[10] = {0, 2, -2, 1, -1, 2, -2, 1, -1};
int n, x, m, y, dp[N][2], cnt, head[N], a, b, now;
struct node { int to, nxt;}e[N << 1];
void Add(int u, int v) { e[++ cnt] = (node) { v, head[u]}; head[u] = cnt;}//
void dfs(int u, int fa) { dp[u][1] = 1;
	Next(i, u) { int v = e[i].to;
		if(fa == v) continue; dfs(v, u);
		dp[u][0] += dp[v][1];
		dp[u][1] += min(dp[v][0], dp[v][1]);
	}
}
signed main() { int T = read();
	while(T --) { a = read(), b = read(); if(a < b) swap(a, b);
		if(a > 2 * b) printf("%d
", b);
		else printf("%d
", (a + b) / 3);
	}
	return 0;
}
原文地址:https://www.cnblogs.com/Flash-plus/p/13834239.html