自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 22:26:06，当前版本为作者最后更新于2020-10-30 18:14:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最近 kkk 传了好多题啊，然后就随便挑了一个（也就是目前编号最大的）来做，拿到了首 A （虽然好像没啥用 。

题意：国王有 $n$ 个儿子，他想要把王位传给年龄超过 $18$ 岁的中最小的儿子。题目保证不存在两个儿子在同一天出生。假设所有年份的 $2$ 月均为 $28$ 天。

考虑先根据生日将所有儿子排序，然后枚举并计算与国王生日的差即可。排序时可以写比较函数，根据年、月、日三个关键字排序。那么怎么计算两个日期之间的间隔呢？

分两种情况：在同一年或不在同一年。

对于在同一年的，我们枚举两个月之间的完整月，将结果加上该月的天数，再通过简单推导计算出两侧零散月的天数即可。

对于不在同一年的，枚举中间年份加上 $365$，然后枚举两侧零散年按照上面类似方法计算即可。

我写的比较暴力，但也很容易理解，因为数据很小就没卡这里的常数。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 105, mx = 18 * 365;
const int month[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int n;
struct Node {
	int d, m, y, id;
	Node(int a=0, int b=0, int c=0, int d=0) : d(a), m(b), y(c), id(d) {}
	~Node() {}
	void read() {scanf("%d%d%d", &this->d, &this->m, &this->y);}
	friend bool operator < (const Node &a, const Node &b) {
		if(a.y != b.y) return a.y < b.y;
		if(a.m != b.m) return a.m < b.m;
		return a.d < b.d;
	}
}king, son[N];

int calc(const Node &a, const Node &b) {
	int res = 0;
	if(a.y == b.y) {
		if(a.m == b.m) return b.d - a.d + 1;
		for(int i=a.m+1;i<b.m;i++) res += month[i];
		res += month[a.m] - a.d + 1 + b.d;
		return res;
	}
	for(int i=a.y+1;i<b.y;i++) res += 365;
	for(int i=a.m+1;i<=12;i++) res += month[i];
	for(int i=1;i<b.m;i++) res += month[i];
	res += month[a.m] - a.d + 1 + b.d;
	return res;
}

int main() {
	king.read();
	scanf("%d", &n);
	for(int i=1;i<=n;i++) son[i].read(), son[i].id = i;
	sort(son+1, son+1+n);
	for(int i=n;i;i--) if(calc(son[i], king) > mx) return printf("%d\n", son[i].id), 0;
	puts("-1");
	return 0;
}