文档章节

序列中求指定和

 阿豪boy
发布于 2017/02/26 14:01
字数 350
阅读 2
收藏 0
点赞 0
评论 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;
}

 

© 著作权归作者所有

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

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

funhacks ⋅ 2017/02/13 ⋅ 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

Dilworth定理 的相关应用

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

anxdada ⋅ 03/29 ⋅ 0

最长递增序列

题目,给定数字序列A,求A中最长的递增序列。 O(n^2)算法思想: 即求以A[j]结尾的最长递增序列L[j] 就相当于求 在序列A中,以排在A[j]前的元素每个元素结尾的最长递增序列,加上A[j]后仍然为...

hgfgoodcreate ⋅ 2015/12/24 ⋅ 0

redis指令

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

庞陆阳 ⋅ 2016/10/27 ⋅ 0

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

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

Garrry ⋅ 2015/07/22 ⋅ 0

面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛 ⋅ 2017/12/22 ⋅ 0

C++ STL学习——algorithm

在之前的博客中我们学习了很多STL中的模板库,包括deque,queue,stack,list等,他们都是一种数据结构,也就是说STL已经为我们实现了。今天我们来讲讲STL中比较大的一个库. 主要是一些算法的...

chenyufeng1991 ⋅ 2016/09/24 ⋅ 0

第9篇-JAVA面向对象-常用类Ⅴ

第9篇-JAVA面向对象-常用类Ⅴ 每篇一句 :巨轮寻深水而航行 初学心得: 没有胆大的猜测就没有伟大的发现 (笔者:JEEP/711)[JAVA笔记 | 时间:2017-04-13| JAVA面向对象 Ⅴ] 1.JAVA Scanner类 ...

JEEP711 ⋅ 2017/06/12 ⋅ 0

Swift2.0语言教程之Swift2.0语言中的标准函数

Swift2.0语言教程之Swift2.0语言中的标准函数 Swift2.0中的标准函数 函数除了可以根据参数列表的有无分为无参函数和有参函数,还可以从定义角度分为用户自定义函数和标准函数两种。以上的示例...

大学霸 ⋅ 2015/07/17 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

mysql in action / alter table

change character set ALTER SCHEMA `employees` DEFAULT CHARACTER SET utf8mb4 DEFAULT COLLATE utf8mb4_general_ci ;ALTER TABLE `employees`.`t2` CHARACTER SET = utf8mb4 , COLLAT......

qwfys ⋅ 今天 ⋅ 0

Java 开发者不容错过的 12 种高效工具

Java 开发者常常都会想办法如何更快地编写 Java 代码,让编程变得更加轻松。目前,市面上涌现出越来越多的高效编程工具。所以,以下总结了一系列工具列表,其中包含了大多数开发人员已经使用...

jason_kiss ⋅ 昨天 ⋅ 0

Linux下php访问远程ms sqlserver

1、安装freetds(略,安装在/opt/local/freetds 下) 2、cd /path/to/php-5.6.36/ 进入PHP源码目录 3、cd ext/mssql进入MSSQL模块源码目录 4、/opt/php/bin/phpize生成编译配置文件 5、 . ./...

wangxuwei ⋅ 昨天 ⋅ 0

如何成为技术专家

文章来源于 -- 时间的朋友 拥有良好的心态。首先要有空杯心态,用欣赏的眼光发现并学习别人的长处,包括但不限于工具的使用,工作方法,解决问题以及规划未来的能力等。向别人学习的同时要注...

长安一梦 ⋅ 昨天 ⋅ 0

Linux vmstat命令实战详解

vmstat命令是最常见的Linux/Unix监控工具,可以展现给定时间间隔的服务器的状态值,包括服务器的CPU使用率,内存使用,虚拟内存交换情况,IO读写情况。这个命令是我查看Linux/Unix最喜爱的命令...

刘祖鹏 ⋅ 昨天 ⋅ 0

MySQL

查看表相关命令 - 查看表结构    desc 表名- 查看生成表的SQL    show create table 表名- 查看索引    show index from  表名 使用索引和不使用索引 由于索引是专门用于加...

stars永恒 ⋅ 昨天 ⋅ 0

easyui学习笔记

EasyUI常用控件禁用方法 combobox $("#id").combobox({ disabled: true }); ----- $("#id").combobox({ disabled: false}); validatebox $("#id").attr("readonly", true); ----- $("#id").r......

miaojiangmin ⋅ 昨天 ⋅ 0

金山WPS发布了Linux WPS Office

导读 近日,金山WPS发布了Linux WPS Office中文社区版新版本,支持大部分主流Linux系统,功能更加完善,兼容性、稳定性大幅度提升。本次更新WPS将首次在Linux提供专业办公文件云存储服务,实...

问题终结者 ⋅ 昨天 ⋅ 0

springboot2输出metrics到influxdb

序 本文主要研究一下如何将springboot2的metrics输出到influxdb maven <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-bo......

go4it ⋅ 昨天 ⋅ 0

微信小程序 - 选择图片显示操作菜单

之前我分享过选择图片这个文章,但是我在实际开发测试使用中发现一个问题在使用 wx.chooseImage 选择照片显示出第一格是拍照,后面是相册里的图片。这种实现之前说过了,效果如下。 但是你从...

hello_hp ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部