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 (≤10 5 ), the total number of diamonds on the chain, and M (≤10 8 ), the amount that the customer has to pay. Then the next line contains N positive numbers D 1 ⋯D N (D i ≤10 3 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给你一连串的钻石，你得用其中一个子串来买东西，在大于应付款的情况下少浪费钱。 我的想法是暴力法，如果子串和刚好等于应付款，就加入答案数组。如果没有一个子串是等于的，就再次遍历，如果找到的子串和比当前最小的子串和小，且大于应付款，就清空答案数组并加入该子串的头尾。如果等于当前最小子串的和，就加入。最后用迭代器输出的话不用加*，只需要it->s即可。但是我这种做法O(N^2)的做法一定是错的，一定会超时 所以用了二分法，二分法有一个条件就必须为递增数组，我们的sum数组刚好为递增数组，sum[i]记录的就是第一个到第i个的和。如果要求i到j的话，就用sum[j] - sum[i-1]。（这个sum数组在序列和经常用得到！！）。 遍历钻石数组的每一位，对其进行二分查找，左端为当前位，右端为第n位。因为sum数组一定是递增的，所以可以用二分查找（复杂度O(NlogN），二分查找我觉得还是挺重要的。特别是那些left和right每次循环完变成啥。这里如果sum[j] - sum[i-1]小于应该支付的钱的话，就去右边继续找，left = mid+1。 如果大于等于，就去左边找，right = mid。然后每次二分查找完这个数字后，就进行判断，它的大于应付钱的最小子串和和当前比哪个更小，大的话就直接continue，小的话就更新答案数组和最小子串he 最后学了怎么两个两个输出
解法一
#include<iostream> #include<vector> using namespace std; struct node{ int s,e; node(int _s, int _e):s(_s), e(_e){} }; int main(){ int n, needPay, diamond; vector<int> chain; vector<node> ans; bool flag = false; cin>>n>>needPay; for(int i = 0; i < n; i++){ cin>>diamond; chain.push_back(diamond); } for(int i = 0; i < n; i++){ int sum = 0; for(int j = i; j < n; j++){ sum += chain[j]; if(sum == needPay){ flag = true; ans.push_back(node(i+1, j+1)); } } } int minPay = 1000000000;//如果没有刚好，就尽量少付一点 if(flag == false){ for(int i = 0; i < n; i++){ int sum = 0; for(int j = i; j < n; j++){ sum += chain[j]; if(sum > needPay && sum < minPay){ minPay = sum; ans.clear(); ans.push_back(node(i+1,j+1)); } else if(sum == minPay && sum > needPay){ ans.push_back(node(i+1, j+1)); } } } } for(auto it = ans.begin(); it != ans.end(); it++){ cout<<it->s<<"-"<<it->e<<endl; } return 0; }解法二
#include<iostream> #include<vector> using namespace std; int n, needPay; void twoPointSearch(vector<int>& sum, int i, int &j, int &tempsum){ int left = i, right = n; while(left < right){ int mid = (left+right)/2; if(sum[mid] - sum[i - 1] < needPay){ left = mid + 1; } else{ right = mid; } } j = right; tempsum = sum[j] - sum[i-1]; } int main(){ int x; cin>>n>>needPay; vector<int> sum;//sum[i]记录的是从0到i的和 vector<int> ans; sum.resize(n+1); for(int i = 1; i <= n; i++){ cin>>sum[i]; sum[i] += sum[i-1]; } int minPay = sum[n]; for(int i = 1; i <= n; i++){ int tempsum = 0, j; twoPointSearch(sum, i, j, tempsum); if(tempsum > minPay) continue; if(tempsum >= needPay){ if(tempsum < minPay){ ans.clear(); minPay = tempsum; } ans.push_back(i); ans.push_back(j); } } for(int i = 0; i < ans.size(); i+=2){ printf("%d-%d\n",ans[i],ans[i+1]); } return 0; }