文档章节

序列中求指定和

 阿豪boy
发布于 2017/02/26 14:01
字数 350
阅读 3
收藏 0

https://www.patest.cn/contests/pat-a-practise/1048

 

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she could only use exactly two coins to pay the exact amount. Since she has as many as 105coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find two coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (<=105, the total number of coins) and M(<=103, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers no more than 500. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the two face values V1 and V2 (separated by a space) such that V1 + V2 = M and V1 <= V2. If such a solution is not unique, output the one with the smallest V1. If there is no solution, output "No Solution" instead.

Sample Input 1:

8 15
1 2 8 7 2 4 11 15

Sample Output 1:

4 11

Sample Input 2:

7 14
1 8 7 2 4 11 15

Sample Output 2:

No Solution

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[])
{
	int n,sum,t;
	vector<int> v; 
	scanf("%d %d",&n,&sum);
	while(n--){
		scanf("%d",&t);
		v.push_back(t);
	}
	
	//由小到大排序 
	sort(v.begin(),v.end());
	 
	int i=0,j=v.size()-1;
	while(i<j){
		if(v[i]+v[j]==sum) break;
		else if(v[i]+v[j]>sum) j--;
		else i++;
	}
	 
 		
	if(i<j)
		printf("%d %d\n",v[i],v[j]);
	else
		printf("No Solution\n"); 
	return 0;
}

 

© 著作权归作者所有

共有 人打赏支持
粉丝 23
博文 1072
码字总数 722196
作品 0
西安
高效的 itertools 模块

itertools 我们知道,迭代器的特点是:惰性求值(Lazy evaluation),即只有当迭代至某个值时,它才会被计算,这个特点使得迭代器特别适合于遍历大文件或无限集合等,因为我们不用一次性将它...

funhacks
2017/02/13
0
0
python中itertools模块介绍---03

product(iterables[,repeat]): 源代码: def product(args,**kwds): pools=map(tuple,args)*kwds.get("repeat",1) result=[[]] for pool in pools: result=[x+[y] for x in result for y in......

指尖跳动的精灵
2015/03/29
0
0
Dilworth定理 的相关应用

讲的好的博客证明 总结一下:给定一个序列, (假定有重复数字, 没有重复的类似推导) 1:如果求每次在其中选出一个不下降子序列并将其删掉, 求删完整个序列所需要的选择子序列的次数 (相当于求...

anxdada
03/29
0
0
走进Python世界(五)数据类型 3. 序列类型-元祖(tuple)

什么是序列 列表,元组和字符串都是序列。 序列的两个主要特点是索引操作符和切片操作符 索引操作符让我们可以从序列中取一个值 切片操作符让我们能够获取序列的一个切片,即一部分序列 索引...

Garrry
2015/07/22
0
0
redis指令

连接控制 QUIT 关闭连接 AUTH (仅限启用时)简单的密码验证 适合全体类型的命令 EXISTS key 判断一个键是否存在;存在返回 1;否则返回0; DEL key 删除某个key,或是一系列key;DEL key1 key2 key...

庞陆阳
2016/10/27
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

49.Nginx防盗链 访问控制 解析php相关 代理服务器

12.13 Nginx防盗链 12.14 Nginx访问控制 12.15 Nginx解析php相关配置(502的问题) 12.16 Nginx代理 扩展 502问题汇总 http://ask.apelearn.com/question/9109 location优先级 http://blog....

王鑫linux
今天
1
0
Nginx防盗链、访问控制、解析php相关配置、Nginx代理

一、Nginx防盗链 1. 编辑虚拟主机配置文件 vim /usr/local/nginx/conf/vhost/test.com.conf 2. 在配置文件中添加如下的内容 { expires 7d; valid_referers none blocked server_names *.tes......

芬野de博客
今天
0
0
spring EL 和资源调用

资源调用 import org.springframework.beans.factory.annotation.Value;import org.springframework.context.annotation.PropertySource;import org.springframework.core.io.Resource;......

Canaan_
今天
1
0
memcached命令行、memcached数据导出和导入

一、memcached命令行 yum装telnet yum install telent 进入memcached telnet 127.0.0.1 11211 命令最后的2表示,两位字节,30表示过期时间(秒) 查看key1 get key1 删除:ctrl+删除键 二、m...

Zhouliang6
今天
1
0
Linux定时备份MySQL数据库

做项目有时候要备份数据库,手动备份太麻烦,所以找了一下定时备份数据库的方法 Linux里有一个 crontab 命令被用来提交和管理用户的需要周期性执行的任务,就像Windows里的定时任务一样,用这...

月夜中徘徊
今天
1
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部