欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 1013. Pairs of Songs With Total Durations Divisible by 60

程序员文章站 2022-05-27 15:26:27
...

leetcode 1013. Pairs of Songs With Total Durations Divisible by 60

题意:一个数组,每个数表示每首歌循环的时间。将所有歌两两匹配,要求满足两首歌持续的总时间能被60整除。求多少种方案。

思路:歌有50000,但是时间只有500。所以考虑将时间都对60取余,统计总个数。

mp[i]表示持续时间为i的歌的数量。

那么对于任意的i,都可以找到60-i进行匹配。

class Solution {
public:
	int numPairsDivisibleBy60(vector<int>& time) {
		map<int, int>mp;
		for (int i = 0; i < time.size(); i++)
			mp[time[i] % 60]++;

		int ans = 0;
		if (mp[0])	ans += mp[0] * (mp[0] - 1)/2;
		for (int i = 1; i < 30; i++)
			if (mp[i] && mp[60 - i])
				
				ans += mp[i] * mp[60 - i];
		if (mp[30])	ans += mp[30] * (mp[30] - 1) / 2;
		return ans;
	}
};

 

相关标签: 离散化