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:
- 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).
- Cut before 5 or after 6, and take off the diamonds from the position 4 to 6 (with values 5+4+6=15).
- 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题目大意：找到和目标值对应的连续子区间，找不到的话就找超过目标值最小的连续子区间。
连续子区间的求和问题可以用前缀和来解决，即sum【i】代表的是从0到i位置的和，sum【j】代表的是从0到j位置的和，那么即sum[i]-sum[j]代表的是从j区域到i区域这一区间的和，仅仅靠这一知识点还是会有一个测试点超时，于是我们继续分析，定义在没有找到准确值的时候最接近目标值的是maxvalue，那么如果到了i位置，从j位置到i位置已经大于maxvalue，那么0到j位置是没有必要讨论的，所以在i-1位置我们找到了准确值，或者更新了maxvalue（此时对应的是j到i-1位置的和），那么我们在i位置的时候就可以直接从j开始，这样也就是最接近maxvalue的位置了。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
int m,n;
scanf("%d%d",&n,&m);
ll i;
ll a[n+1];
ll sum[n+1];
memset(sum,0,sizeof(sum));
for(i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(i==1)sum[i]=a[i];
else sum[i]=sum[i-1]+a[i];//前缀和
}
int j;
int maxvalue=INT_MAX;
bool flag=1;
vector<int>ans;
int l=0;//L为从哪个开始
for(i=1;i<=n;i++){
for(j=l;j<=i;j++){
int res=sum[i]-sum[j];
if(res<m)break;
else if(res==m){
l=j;//更新起始位置
flag=0;
printf("%d-%d\n",j+1,i);
}
else if(res>m&&res<maxvalue){
l=j;
maxvalue=res;
ans.clear();
ans.push_back(j+1);
ans.push_back(i);
}
else if(res==maxvalue){
l=j;
ans.push_back(j+1);
ans.push_back(i);
}
}
}
if(flag){
for(i=0;i<ans.size();i+=2){
printf("%d-%d\n",ans[i],ans[i+1]);
}
}
system("pause");
}
?
