六月集训第四日-贪心

题目描述：

1221. 分割平衡字符串 - 力扣（LeetCode）

在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

**注意：**分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。

返回可以通过分割得到的平衡字符串的 最大数量 。

我的题解：

int balancedStringSplit(char * s){
    int count=0;
    int max=0;
    int len=strlen(s);
    for(int i=0;i<len;i++){
       int k=(s[i]=='R')?1:-1;
        max+=k;
        if(max==0){
            //说明肯定要由r和其抵消
            //所以总数++
            count++;
        }
    }
    return count;
}

我的思路：

分割贪心，如果前面是平衡那么后面平衡肯定能使全部都是平衡的，所以一直往前排就行

有点类似找对子数的思想

题目描述：

1217. 玩筹码 - 力扣（LeetCode）

有 n 个筹码。第 i 个芯片的位置是 position[i] 。

我们需要把所有筹码移到同一个位置。在一步中，我们可以将第 i 个芯片的位置从 position[i] 改变为:

• position[i] + 2 或 position[i] - 2 ，此时 cost = 0

• position[i] + 1 或 position[i] - 1 ，此时 cost = 1

  返回将所有筹码移动到同一位置上所需要的 最小代价

我的题解：

int minCostToMoveChips(int* position, int positionSize){
 int odd=0,even=0;//记录奇数，偶数
 for(int i=0;i<positionSize;++i)
    position[i]%2==0?even++:odd++;
 return odd>even?even:odd;
}

我的思路：

贪心策略：尽可能多的用代价0的方式移动
 如果是位置固定位偶数位，则奇数位移动一位加上移动偶数次+1，偶数位开销为0
 如果位置是奇数，则原本奇数位置移动代价为0，偶数为1

题目描述：

1029. 两地调度 - 力扣（LeetCode）

公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。

第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。

返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。

我的题解：

int cmp(const void*a,const void* b){
    return ((*(int**)a)[0]-(*(int**)a)[1])-((*(int**)b)[0]-(*(int**)b)[1]);
}

int twoCitySchedCost(int** costs, int costsSize, int* costsColSize){
    qsort(costs,costsSize,sizeof(int*),cmp);
    int sum=0;
   for(int i=0;i<costsSize;++i){
       if(i<costsSize/2){
           sum+=costs[i][0];
       }else{
           sum+=costs[i][1];
       }
   } 
   return sum;
}

我的思路：

感觉贪心的题真的很脑筋急转弯哎。。

遍历一遍costs，选两个下标中数值较小的那一个，
但是这样的话，不能保证两地都有n个

如何保证能保持两边一样呢？

就按排序的决定因素costs[i][0] - costs[i][1],即二者差值去排序

这样，对前n个选择0下标，后n个选择1下标