# 一、题目

## 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 }```

# 三、程序

```#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

res.push_back(n);

res.push_back(n - 1);

sum = 12 + 11 - 7 = 16

x = 8, y = 8

sum = 9 + 7 - 7 = 9

x = 4, y = 5

241 篇文章45 人订阅

0 条评论

## 相关文章

2577

### javascript基础重点

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

952

### A Bite of GoLang(上)

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

55610

1504

### 《Objective-C基础教程》笔记

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

832

### XML编程知识点总结

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

802

913

### 深入浅出事件流处理NEsper（二）

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

20010

3488

2409