PAT1044 Shopping in Mars-Toy模板网

这篇具有很好参考价值的文章主要介绍了PAT1044 Shopping in Mars。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

个人学习记录，代码难免不尽人意。
做了这么多题难得本题不看答案一遍过，很是激动。

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.
PAT1044 Shopping in Mars,PTA,算法,c++,pat
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<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
using namespace std;
int num[100010];
int main(){
   int n,m;
   scanf("%d%d",&n,&m);
   for(int i=0;i<n;i++){
   	scanf("%d",&num[i]);
   }
   int i=0,j=0;
   int temp=0;
   bool flag=false;
   int cost=1000000000;
   vector<pair<int,int> > v;
   int count=0;
   while(i<n||j<n){
//   	cout << i << " " <<j << endl;
   	if(temp<m){
   		if(j==n) break;
   		temp+=num[j];
   		j=min(n,j+1);
	   }
	else if(temp==m){
		flag=true;
		printf("%d-%d\n",i+1,j);
		if(j+1<n){
			temp=temp-num[i]+num[j];
			j++;
		}
		else{
		j=min(n,j+1);
		temp=temp-num[i];
		} 
		i=min(n,i+1);
		
	}
	else{
		if(temp<cost){
			cost=temp;
			v.clear();
			v.push_back(make_pair(i+1,j));
		}
		else if(temp==cost){
			v.push_back(make_pair(i+1,j));
		}
	        temp-=num[i];
			i=min(n,i+1);
			
	}
   }

   if(!flag&&!v.empty()){
   	for(int k=0;k<v.size();k++){
   		printf("%d-%d\n",v[k].first,v[k].second);
	   }
   	
   }
   return 0;
}

利用了《算法笔记》中讲述的“two points”思想，设置了i，j两个下标来从左到右遍历数组，其中记录num[i]到num[j]的和temp，判断temp和m的关系，分为三种情况：①如果temp小于m，则让j++，如果j已经等于边界n，则说明不可能再得到新结果了，直接break。②如果temp等于m，则此时i和j就是我们想要输出的结果，直接输出，然后让i和j都加一，相应的temp减去num[i]加上num[j]的值。③如果temp大于m，则让i++，相应的减去temp对应的值。文章来源地址https://www.toymoban.com/news/detail-642458.html

到了这里，关于PAT1044 Shopping in Mars的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！