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

原文发布于微信公众号 - 海天一树(gh_de7b45c40e8b)

原文发表时间:2018-05-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IMWeb前端团队

20个例子入门Q.js

本文希望通过20个简单的例子让没用过Q.js的同学快速掌握其基本用法 1. 新建实例 html代码: <div id="demo" q-text="msg"><...

2577
来自专栏LIN_ZONE

javascript基础重点

1.在javascript中使用 == 比较,会自动转换数据类型再比较,有时候会 得到非常诡异的结果;一般情况下使用 === 比较,它不会自动转换数据类型,如果...

952
来自专栏盛国存的专栏

A Bite of GoLang(上)

A bite of GoLang(浅尝GoLang),本文只是Go语言的冰山一角,本文包含作者学习Go语言期间积累的一些小的经验,同时为了方便让读者了解到Go语...

55610
来自专栏Jackson0714

PHP内核之旅-3.变量

1504
来自专栏nimomeng的自我进阶

《Objective-C基础教程》笔记

1.xcode中,oc的.m文件代表message,指的是Objective-C的一个主要特性。 2.NS前缀的来历要追溯到次公局包还被成为NextStep,...

832
来自专栏个人分享

XML编程知识点总结

DOM的全称是Document Object Model,也即文档对象模型。基于DOM的XML分析器将一个XML文档转换成一个对象模型的集合,应用程序挣是通过...

802
来自专栏博客园

Core官方DI解析(4)--CallSiteRuntimeResolver

这两个类都在其CallSiteVisitor<TArgument, TResult>基类中

913
来自专栏张善友的专栏

深入浅出事件流处理NEsper(二)

NEsper使用的事件类型来描述事件的类型信息。你的应用在启动时可能预先配置定义事件类型,或者在运行时通过API或EPL语法动态的增加事件类型。 EPL中的cr...

20010
来自专栏前端杂货铺

前端开发中的字符编码

前端开发过程中会接触各种各样的编码,比较常见的主要是UTF-8和HTML实体编码,但是web前端的世界却不止这两种编码,而且编码的选择也会造成一定的问题,如前后...

3488
来自专栏偏前端工程师的驿站

JS魔法堂:那些困扰你的DOM集合类型

一、前言                                     大家先看看下面的js,猜猜结果会怎样吧!   可选答案:   ①. 获取id属...

2409

扫码关注云+社区

领取腾讯云代金券