正文索引 [隐藏]

传送门

t1 圆形赛道上经过次数最多的扇区

有一个圆形区域，被分成n块扇区，给出一系列起点与终点，问跑到最后经过次数最多的扇区是哪些。

赛时居然没过这题…

当时写了一个模拟，因为没处理好边界问题，死活过不去。赛后下来看了发现确实想复杂了。

我们要发现一个事实，因为赛道是圆形的，所以除了结尾的那一圈“不完整”的赛程，之前若干圈赛程都是没有意义的，因为每个扇区都同时累加了经过次数，“同时”在本题中是没有讨论意义的。所以我们的答案只用关注最后那不完整的赛程经过了哪些扇区。

值得注意的是，起点不一定是第一块扇区，所以要处理越界问题。同时，观察样例不难发现答案是有序的，所以还要对最终答案数组做一个排序。

class Solution {
public:
    vector<int> mostVisited(int n, vector<int>& rounds) {
        vector<int>ans;
        int l = rounds[0];
        int r = rounds[rounds.size()-1];

        while(l != r)
        {
            if(l == n+1)
            {
                l %= n;
                continue;
            }
            ans.push_back(l++);
        }
        ans.push_back(r);
        sort(ans.begin(),ans.end());
        
        return ans;
    }
};

t2 你可以获得的最大硬币数目

你和Alice还有Bob取一共有3n颗的一堆硬币。每次拿出三小堆，Alice拿最多的，Bob拿最少的，剩下那堆给你，问你最多能拿多少硬币。

我确实不知道这题为什么会是中等，为什么会在第二题，这真是我做过最简单的中等题了。

没啥好说的，不难想出贪心的做法：排序，每次操作从队首取一堆、队末取两堆，直到没有硬币。

class Solution {
public:
    int maxCoins(vector<int>& piles) {
        int n = piles.size();
        sort(piles.begin(), piles.end());
        int ans = 0;
        
        n = (n + 1) / 3;
        
        int a = 0, b = piles.size() - 2, c = piles.size() - 1;
        for(int i = 0; i < n; i++)
        {
            ans += piles[b];
            
            a++;
            b -= 2;
            c -= 2;
        }
        
        return ans;
    }
};

第一次写的时候居然用vector的pop与erase来维护队首队尾，直接超时。所以后面才改成下标操作。我发誓这是我干过最蠢的事情。