Ice Cream Parlor

Authored by  on Mar 21 2013

Problem Statement

Sunny and Johnny together have M dollars they want to spend on ice cream. The parlor offers N flavors, and they want to choose two flavors so that they end up spending the whole amount.

You are given the cost of these flavors. The cost of the ith flavor is denoted by ci. You have to display the indices of the two flavors whose sum is M.

Input Format

The first line of the input contains T; T test cases follow. 

Each test case follows the format detailed below: The first line contains M. The second line contains N. The third line contains N space-separated integers denoting the price of each flavor. Here, the ith integer denotes ci.

Output Format

Output two integers, each of which is a valid index of a flavor. The lower index must be printed first. Indices are indexed from 1 to N.

Constraints

1≤T≤50 

2≤M≤10000 

2≤N≤10000 

1≤ci ≤10000,where i∈[1,N] 

The prices of any two items may be the same and each test case has a unique solution.

Sample Input

2451 4 5 3 2442 2 4 3

Sample Output

1 41 2

Explanation

The sample input has two test cases. 

For the 1st, the amount M = 4 and there are 5 flavors at the store. The flavors indexed at 1 and 4 sum up to 4. 

For the 2nd test case, the amount M = 4 and the flavors indexed at 1 and 2 sum up to 4.

Solution

简单题。

利用题目给出的cost数组构造index数组，index[i]表示i在cost数组中首次出现的位置。

Implementation

 

#include
             
              using namespace std;const int N(1e4+5);int idx[N];int main(){
             	freopen("in", "r", stdin);	int T; 	cin>>T;	for(int n, m, id1, id2; T--; memset(idx, 0, sizeof(idx))){
             		cin>>m>>n;		for(int i=1, c; i<=n; i++){
             			cin>>c;			if(c>=m) continue;	//error-prone			if(!idx[c]) idx[c]=i;			if(idx[m-c]&&idx[m-c]!=i){
             				id1=idx[m-c], id2=i;	//error-prone			}		}		cout<
              
               <<' '<
               
                <
               
              
             

凡注释error-prone的地方都是开始写错了的。

1. 我的写法是边读入边处理的，有时会没读完就得出答案，这时很容易就来个break;

2. 针对这道题的

　　2.1 要预判c>=m的情况

　　2.2 如何处理cost相同的flavor