2018 TCO Algorithm-Round 1B 600-points题解报告

一、题目

Problem Statement

Consider the set of integers between 1 and n, inclusive, and two positive integers c and k. You want to build an ordered list of k pairs (x1, y1), (x2, y2), … (xk, yk) such that the following conditions are met. 1 ≤ xi < yi ≤ n for all i between 1 and k, inclusive. yi < xi+1 for all i between 1 and k-1, inclusive. (xi+1 + yi+1) - (xi + yi) = c for all i between 1 and k-1, inclusive. If a list of pairs satisfies all of the above conditions, the list is said to be stable. For any fixed n, c, and k, a stable list of k pairs is said to be maximal if its sum of elements (the sum of all 2k integers it contains) is the largest among all stable lists of k pairs. For instance, consider n=5, c=4, and k=2. There are two stable lists of pairs: one is [(1, 2), (3, 4)] and the other is [(2, 3), (4, 5)]. The latter is the only maximal stable list of pairs in this example as its sum is (2+3+4+5) = 14.

Given n, c, and k, find one maximal stable list of pairs, and return a vectorthat describes the list. Specifically, if (x1, y1), (x2, y2), …, (xk, yk) is your maximal stable list of pairs, you must return { x1, y1, x2, y2, …, xk, yk }. If there are many maximal stable lists of pairs, you may return any one of them. If no stable list of pairs with the desired properties exists, you must return an empty vector.

Definition

Class: StablePairsDiv1 Method: findMaxStablePairs Parameters: int, int, int Returns: vector Method signature:vectorfindMaxStablePairs(int n, int c, int k) (be sure your method is public)

Limits

Time limit (s): 2.000 Memory limit (MB): 256

Constraints

• n will be between 1 and 100, inclusive.
• c will be between 1 and 100, inclusive.
• k will be between 1 and 100, inclusive.

Examples

0)
5
4
2
Returns: {2, 3, 4, 5 }
This example was described in the problem statement.
1)
4
4
2
Returns: {1, 2, 3, 4 }
2)
1
100
1
Returns: { }
When n=1, regardless of c and k, there is no way to build a pair.
3)
3
100
1
Returns: {2, 3 }
With k=1 we are looking for stable lists that only contain a single pair of numbers. There are three stable lists: [(1, 2)], [(1, 3)], and [(2, 3)]. Obviously, the last one is the only maximal one in this case.
4)
10
6
3
Returns: {2, 5, 6, 7, 9, 10 }
5)
12
7
3
Returns: {4, 5, 6, 10, 11, 12 }

二、分析

本题比较简单，按从大到小的顺序把数字放到vector中，这样可以保证和最大。最后再把vector的元素顺序反转即可

三、程序

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
class StablePairsDiv1
{
public:
    vector<int> findMaxStablePairs(int n, int c, int k)
    {
        vector<int> res;
        if(1 == k)
        {
            res.push_back(n - 1);
            res.push_back(n);
            if(1 == n)
            {
                res.clear();
            }
            return res;
        }
        if(c < 4)
        {
            // 结果必然为空，比如n=4,c=3,k=2
            return res;
        }
        res.push_back(n);
        res.push_back(n - 1);
        for(int i = 0; i < k - 1; ++i)
        {
            int sum = res.back() + res[res.size() - 2] - c;
            int x = sum / 2;
            int y = sum - x;
            while(x == y)
            {
                --x;
                ++y;
            }
            res.push_back(y);
            res.push_back(x);
        }
        if(res.back() <= 0)
        {
            res.clear();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
int main()
{
    StablePairsDiv1 s;
    vector<int> ans = s.findMaxStablePairs(12, 7, 3);
    vector<int>::iterator it;
    for(it = ans.begin(); it != ans.end(); it++)
    {
        cout << *it << ' ';
    }
    return 0;
}

运行结果：

4 5 7 9 11 12

下面以n = 12, c = 7, k = 3重点分析一下for循环。

在for循环之前，

res.push_back(n);

res.push_back(n - 1);

这两句是把12和11先后放到res中。

第一次for循环，i = 0

sum = 12 + 11 - 7 = 16

x = 8, y = 8

因为x == y，if条件为真，x自减变为7，y自减变为9

再把9和7先后放到res中，此时res中的元素按顺序排列为12,11,9,7

第二次for循环，i = 1

sum = 9 + 7 - 7 = 9

x = 4, y = 5

把5和4先后放到res中，此时res中的元素按顺序排列为12, 11, 9, 7, 5, 4

接下来，i自加变为2, i < k - 1不成立，for循环结束。

再通过reverse函数，res中的元素按顺序排列为4，5，7，9，11，12