首页 > 代码库 > POJ-1247

POJ-1247

#include<iostream>
#include<vector>
using namespace std;

/**
 * return:
 * 		-1:can not find;
 * 		positive:find the first position;
 */
int findPosition(vector<int> v,int size, int requestHalfSum){
	int sum=0;
	for(int i=0;i<size;i++){
		sum+=v[i];
		if(sum>requestHalfSum){
			return -1;
		}else if(sum==requestHalfSum){
			return i+1;
		}
	}

	return -1;
}

int main(int argc, char *argv[]){
	int n;
	while(cin>>n){
		int totalRequest=0;
		if(n==0){
			break;
		}
		vector<int> guestRequest(n);
		for(int i=0;i<n;i++){
			cin>>guestRequest[i];
			totalRequest+=guestRequest[i];
		}

		if(totalRequest%2!=0){
			cout<<"No equal partitioning."<<endl;
			continue;
		}

		int index=findPosition(guestRequest, n, totalRequest/2);

		if(index==-1){
			cout<<"No equal partitioning."<<endl;
		}else{
			cout<<"Sam stops at position "<<index<<" and Ella stops at position "<<index+1<<"."<<endl;
		}
	}
	return 0;
}

POJ-1247