Ambiguous Dates Gym-101522A

本文主要是介绍Ambiguous Dates Gym-101522A，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Ambiguous Dates Gym-101522A

标签：思维&逻辑

---

题目链接

解法一

/*题意：日期有两种表示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 <stdio.h>
#include <algorithm>
using namespace std;#define maxn 100005
int 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 <stdio.h>
#include <algorithm>
using namespace std;#define maxn 100005
int 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;
}

这篇关于Ambiguous Dates Gym-101522A的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---