题解 [email protected]洛谷 【[NWRRC2016]King’s Heir】

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


题意:国王有 nn 个儿子,他想要把王位传给年龄超过 1818 岁的中最小的儿子。题目保证不存在两个儿子在同一天出生。假设所有年份的 22 月均为 2828 天。

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

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

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

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

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


代码:

//By: [email protected]_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;
}