pat1044. Shopping in Mars (25)
1044. Shopping in Mars (25)
Shopping in Mars is quite a different experience. The Mars people pay by chained diamonds. Each diamond has a value (in Mars dollars M$). When making the payment, the chain can be cut at any position for only once and some of the diamonds are taken off the chain one by one. Once a diamond is off the chain, it cannot be taken back. For example, if we have a chain of 8 diamonds with values M$3, 2, 1, 5, 4, 6, 8, 7, and we must pay M$15. We may have 3 options:
1. Cut the chain between 4 and 6, and take off the diamonds from the position 1 to 5 (with values 3+2+1+5+4=15).
2. Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15).
3. Cut before 8, and take off the diamonds from the position 7 to 8 (with values 8+7=15).
Now given the chain of diamond values and the amount that a customer has to pay, you are supposed to list all the paying options for the customer.
If it is impossible to pay the exact amount, you must suggest solutions with minimum lost.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 numbers: N (<=105), the total number of diamonds on the chain, and M (<=108), the amount that the customer has to pay. Then the next line contains N positive numbers D1 ... DN (Di<=103 for all i=1, ..., N) which are the values of the diamonds. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print "i-j" in a line for each pair of i <= j such that Di + ... + Dj = M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i.
If there is no solution, output "i-j" for pairs of i <= j such that Di + ... + Dj > M with (Di + ... + Dj - M) minimized. Again all the solutions must be printed in increasing order of i.
It is guaranteed that the total value of diamonds is sufficient to pay the given amount.
Sample Input 1:
16 15
3 2 1 5 4 6 8 7 16 10 15 11 9 12 14 13
Sample Output 1:
1-5
4-6
7-8
11-11
Sample Input 2:
5 13
2 4 5 7 9
Sample Output 2:
2-4
4-5
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#include<string>
#include<map>
#include<set>
using namespace std;
vector<pair<int,int> > line;
#define inf 100000005
int main(){
//freopen("D:\\INPUT.txt","r",stdin);
int minsum;//历史上的最小值
int n,sum,i,j;
scanf("%d %d",&n,&sum);//规定的最小值
int *dia=new int[n+];
for(i=;i<=n;i++){
scanf("%d",&dia[i]);
}
dia[]=dia[];
j=;//虚拟0位置还有数
int cursum=dia[]+dia[];//当前的最小值
minsum=inf;
line.push_back(make_pair(,));
for(i=;i<=n;i++){//指针思想
cursum-=dia[i-];
while(j<n&&cursum<sum){
cursum+=dia[++j];
}
if(cursum>=sum&&cursum<minsum){//update
//这里的cursum>=sum是针对j已经到数组末尾设立的
//j之前如果已经到末尾,i向后移动有可能cursum有可能等于sum,但一定是减少的
line.clear();
line.push_back(make_pair(i,j));
minsum=cursum;
}
else{
if(cursum==minsum){//insert
line.push_back(make_pair(i,j));
}
}
}
for(i=;i<line.size();i++){
printf("%d-%d\n",line[i].first,line[i].second);
}
return ;
}
最新文章
- *** wechat-php-sdk 微信公众平台php开发包
- RCP:利用actionSet在菜单(menu)里添加内容
- 浅谈JSON数据解析方法
- KSFramework常见问题:Lua脚本热重载,内存状态数据丢失?
- Swift 1.0: missing argument label &#39;xxx&#39; in call
- [原创]Java中的字符串比较,按照使用习惯进行比较
- 典型的字符串处理代码(page50)
- 动画气泡指示当前滑动值--第三方开源--DiscreteSeekbar
- 【BZOJ】【3524】【POI2014】Couriers
- Android(java)学习笔记101:WindowManager 中LayoutParams的各种属性
- hdoj 3400 三分
- HeadFirst设计模式读书笔记(3)-装饰者模式(Decorator Pattern)
- Nginx 怎么给一台服务器,配置两个域名?详细的解说+截图教程
- 2019.03.25 NOIP训练 匹配(match)(贪心)
- shell脚本删除log日志
- .NET手记-ASP.NET MVC快速分页的实现
- Xcode连接TFS Git用户名和密码不正确解决方案
- django重定向是如何实现的,用的什么状态码?
- if语句中的 == 和= 区别
- .net通过url访问服务器获取服务器返回数据