LeetCode 第 23 场双周赛（970/2044，前47.5%）

示例 1：
输入：n = 13
输出：4
解释：总共有 9 个组，将 1 到 13 按数位求和后这些组分别是：
[1,10]，[2,11]，[3,12]，[4,13]，[5]，[6]，[7]，[8]，[9]。
总共有 4 个组拥有的数字并列最多。

示例 2：
输入：n = 2
输出：2
解释：总共有 2 个大小为 1 的组 [1]，[2]。

示例 3：
输入：n = 15
输出：6

示例 4：
输入：n = 24
输出：5
 
提示：
1 <= n <= 10^4

class Solution {
public:
    int countLargestGroup(int n) {
        unordered_map<int,int> m;
        int sum;
        for(int i = 1; i <= n; ++i)
        {
            sum = cal(i);
            m[sum]++;
        }
        int maxlen = 0, count = 0;
        for(auto mi : m)
        {
            if(mi.second > maxlen)//和一样的，个数最多的
            {
                maxlen = mi.second;
                count = 1;
            }
            else if(mi.second == maxlen)
                count++;
        }
        return count;
    }
    int cal(int i)
    {	//计算各数位的和
        int sum = 0;
        while(i)
        {
            sum += i%10;
            i /= 10;
        }
        return sum;
    }
};

示例 1：
输入：s = "annabelle", k = 2
输出：true
解释：可以用 s 中所有字符构造 2 个回文字符串。
一些可行的构造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"

示例 2：
输入：s = "leetcode", k = 3
输出：false
解释：无法用 s 中所有字符构造 3 个回文串。

示例 3：
输入：s = "true", k = 4
输出：true
解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。

示例 4：
输入：s = "yzyzyzyzyzyzyzy", k = 2
输出：true
解释：你只需要将所有的 z 放在一个字符串中，所有的 y 放在另一个字符串中。
那么两个字符串都是回文串。

示例 5：
输入：s = "cr", k = 7
输出：false
解释：我们没有足够的字符去构造 7 个回文串。
 
提示：
1 <= s.length <= 10^5
s 中所有字符都是小写英文字母。
1 <= k <= 10^5

class Solution {
public:
    bool canConstruct(string s, int k) {
        if(s.size() < k)
            return false;
        int count[26] = {0};
        for(int i = 0; i < s.size(); ++i)
            count[s[i]-'a']++;
        int odd = 0;
        for(int i = 0; i < 26; ++i)
        {
            if(count[i]%2 == 1)
                odd++;
        }       
        return odd <= k;
    }
};

class Solution {
public:
    bool checkOverlap(int r, int xc, int yc, int x1, int y1, int x2, int y2) {
        if(dis(xc,yc,x1,y1)<=r*r||dis(xc,yc,x1,y2)<=r*r||dis(xc,yc,x2,y1)<=r*r||dis(xc,yc,x2,y2)<=r*r)
            return true;
        if(x1<=xc && xc <= x2 &&  y1-r <= yc && yc <= y2+r)
            return true;
        if(x1-r<=xc && xc <= x2+r &&  y1 <= yc && yc <= y2)
            return true;
        return false;
    }

    double dis(int xc, int yc, int x, int y)
    {
        return pow((xc-x),2)+pow((yc-y),2);
    }
};

bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) 
    {
        double x0 = (x1 + x2) / 2.0;
        double y0 = (y1 + y2) / 2.0;

        vector<double> p = { abs(x_center - x0) , abs(y_center - y0) };
        //圆心与矩形中心的坐标差
        vector<double> q = { x2 - x0, y2 - y0 };
		//矩形中心与一个顶点的坐标差
        double a1 = max(p[0] - q[0], 0.0);//在上述两个矩形内的话，一个分量为0
        double a2 = max(p[1] - q[1], 0.0);//在四个圆角处，两个量都不为0
        return sqrt(a1 * a1 + a2 * a2) <= radius;   
    }

示例 1：
输入：satisfaction = [-1,-8,0,5,-9]
输出：14
解释：去掉第二道和最后一道菜，最大的喜爱时间系数和为 (-1*1 + 0*2 + 5*3 = 14) 。
每道菜都需要花费 1 单位时间完成。

示例 2：
输入：satisfaction = [4,3,2]
输出：20
解释：按照原来顺序相反的时间做菜 (2*1 + 3*2 + 4*3 = 20)

示例 3：
输入：satisfaction = [-1,-4,-5]
输出：0
解释：大家都不喜欢这些菜，所以不做任何菜可以获得最大的喜爱时间系数。

示例 4：
输入：satisfaction = [-2,5,-1,0,3,-3]
输出：35

提示：
n == satisfaction.length
1 <= n <= 500
-10^3 <= satisfaction[i] <= 10^3

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.rbegin(), satisfaction.rend());
        int sum = 0, ans = 0;
        for(int i = 0; i < satisfaction.size(); ++i)
        {
        	sum += satisfaction[i];//满意度大的加上
        	if(sum <= 0)
        		break;
        	ans += sum;//循环一次，最大的多加1次，相当于系数+1
        }
        return ans;
    }
};

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());//需要先排序
        int i, j, n = satisfaction.size();
        vector<vector<int>> dp(n+1, vector<int>(n+1,0));
        //dp[i][j] 表示前i道菜，做j道的最大满意度
        dp[1][0] = 0, dp[1][1] = satisfaction[0];
        for(i = 2; i <= n; ++i)
        {
        	for(j = 1; j <= i; ++j)
        	{
        		if(j == i)
        			dp[i][j] = dp[i-1][j-1]+j*satisfaction[i-1];//每道菜都做了
        		else
        			dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+j*satisfaction[i-1]);
        			//第i道菜不做，dp[i-1][j]，第i道菜做 dp[i-1][j-1]+j*satisfaction[i-1]
        	}
        }
        int ans = INT_MIN;
        for(i = 0; i <= n; ++i)
        	ans = max(ans, dp[n][i]);//n道菜，做i道的最大值
        return ans;
    }
};