本文共 1304 字，大约阅读时间需要 4 分钟。
标签：思维&逻辑
解法一
/* 题意：日期有两种表示day/month/year 或 month/day/year， 7/8/2017(8/7/2017)是引起歧义的, 而15/8/2017和10/10/2017则不会， 要求重新排列月份，使得引起歧义的日期最少， 一年可以有M月(1 <= M <= 10^5)，每月有D天(1 <= D <= 10^5)。 分析：某个月份的天数越多，这个月就应该越靠后。排序后，计算引起歧义的日期数量即可。*/#include#include using namespace std;#define maxn 100005int month[maxn], M;int main(){ while(scanf("%d", &M) != EOF){ int i, top = 1; __int64 num = 0, ans = 0; for(i = 1; i <= M; i++) scanf("%d", &month[i]); sort(month + 1, month + M + 1); for(i = 1; i <= M; i++) if(month[i] > i) ans += 2 * min(month[i] - i, M - i); printf("%lld\n", ans); } return 0;}
解法二
#include#include using namespace std;#define maxn 100005int month[maxn], M;int main(){ while(scanf("%d", &M) != EOF){ int i, top = 1; __int64 num = 0, ans = 0; for(i = 1; i <= M; i++) scanf("%d", &month[i]); sort(month + 1, month + M + 1); for(i = 1; i <= M; i++){ while(i != 1 && top < i && month[top] < i){ top++; num--; } //printf("num: %d\n", num); ans += num; num++; } printf("%lld\n", ans * 2); } return 0;}
转载地址：http://nskxi.baihongyu.com/