【算法一】到天宫做客【模板】

问题讨论区 基础段
1

题目ID：1345

题目描述

有一天，我做了个梦，梦见我很荣幸的接到了猪八戒的邀请，到天宫陪他吃酒。我犹豫了。天上一日，人间一年啊！当然，我是个闲人，一年之中也没有多少时日是必须在人间的，因此，我希望选一个最长的空闲时间段，使我在天上待的时间尽量长(首尾两天不计入)。记住，今年是4000年。天上一天也是24小时，每小时60分，每分60秒。

输入格式：

输入文件的第一行是一个非负整数 N，表示4000年中必须呆在人间的天数，以下共N行，每行两个用空格隔开的正整数，即日期（月,日），输入文件保证无错误，日期无重复。

输出格式：

输出文件仅有一行包含一个非负整数，即在天上的时间(四舍五入精确到秒)。

样例输入：

2
3 8
12 2

样例输出：

63266

代码如下：

#include <iostream>
#include <algorithm>
#include <climits>
#include <iomanip>

using namespace std;

double month[] = {0, 31, 29, 31, 30, 30, 31, 31, 30, 31, 30, 31};

typedef struct {
	int month;
	int day;
} Node;

Node node[400];

bool cmp(Node a, Node b) {
	if (a.month != b.month) {
		return a.month < b.month;
	} else {
		return a.day < b.day;
	}
}

int main(void) {
	int n;
	
	cin >> n;
	
	for (int i = 1; i <= n; i++) {
		cin >> node[i].month >> node[i].day;
	}
	
	sort(node+1, node+1+n, cmp);
	
	int MAX_D = INT_MIN;
	
	for (int i = 1; i < n; i++) {
		int cnt = 0;
		if (node[i].month == node[i+1].month) {
			MAX_D = max(MAX_D, node[i+1].day-node[i].day-1);
			continue;
		}
		
		for (int j = node[i].month+1; j < node[i+1].month; j++) {
			cnt += month[j];
		}
		
		cnt += month[node[i].month] - node[i].day;
		cnt += node[i+1].day - 1;
		MAX_D = max(cnt, MAX_D);
	}
	
	int ans = 0;
	for (int i = 1; i < node[1].month; i++) {
		ans += month[i];
	}
	ans += node[1].day - 1;
	MAX_D = max(ans, MAX_D);
	
	ans = 0;
	for (int i = 12; i > node[n].month; i--) {
		ans += month[i];
	}
	ans += month[node[n].month] - node[n].day;
	MAX_D = max(ans, MAX_D);
	
	cout << fixed << setprecision(0) << (MAX_D * 1.0 / 366) * 86400;
	
	return 0;
}
3 个赞
2