TopCoder SRM676(Div.1) Easy ANewHope

Posted on By 二价氢

题目大意

给定两个数列,每组操作可以把每个数向后移动位或向前移动任意位,问最少需要多少组操作。

原题:

假设一周有天,一个人有件衣服,每天穿一件,每周不重复,洗一件衣服需要天之后才能穿,给定第一周和最后一周穿衣服的情况,问最少需要多少周才能实现。

(这题又叫:氢酱换袜子~)

解法

如果某一件衣服最后一周穿的时间在第一周穿的时间之后,那么这件衣服肯定是没有限制的。

也就是说,周穿的衣服下一周最早在周才能穿,发现了这一点之后,模拟即可。

Code

class ANewHope {
public:
    int count(vector<int> firstWeek, vector<int> lastWeek, int D) {
        int n = firstWeek.size();
        int maxDelta = n - D, ans = 1;
        for (int x = 0; x < n; x++)
            for (int y = 0; y < x; y++)
                if (firstWeek[x] == lastWeek[y])
                    ans = max(ans, (x - y + maxDelta - 1) / maxDelta + 1);
        return ans;
    }
};

Level Upper 2016 - TopCoder 250 : 5 / 5