首页 > 专题系列 > Java解POJ > POJ 3425 Customer support [解题报告] Java
2013
11-12

POJ 3425 Customer support [解题报告] Java

Customer support

问题描述 :

Customer support department in an "Incomprehension Amateurs, Ltd" software company has call center for answering users’ questions. Support prices are as follows:

1. Answer to a question 10 USD
2. Correct answer to a question 20 USD
3. Correct answer to a question with explanation 40 USD
4. Correct answer to a question which was already correctly answered before +10 USD for each previous correct answerD

So, for example, if user asks the same question three times, first receives incorrect answer, then correct one, and the third time correct answer with explanation, it will cost him 10 + 20 + (40 + 1 * 10) = 80 USD.

Customers are billed monthly according to call log. Company engineers review the log and for each question determine:

1. unique number, so the equivalent questions have same numbers,
2. whether the answer was correct,
3. whether the answer was short or included detailed enough explanation.

Given that data, your program must calculate the payment amount.

输入:

Input file contains number of calls N followed by N triples qi ai xi, where qi is integer question number, ai = 1 if the answer was correct, 0 otherwise, xi = 1 if explanation was given, 0 otherwise.

Constraints

1 ≤ N ≤ 10000, 1 ≤ qi ≤ 106.

输出:

Output file must contain a single number — payment amount.

样例输入:

Sample Input 1
1
9834 0 1
Sample Input 2
3
33 1 0
33 0 0
33 1 1

样例输出:

Sample Output 1
10
Sample Output 2
80

温馨提示:

Bold texts appearing in the sample sections are informative and do not form part of the actual data.

解题代码:

//* @author: Yeming Hu"[email protected]"
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	Call[] calls = new Call[n];
	for(int i = 0; i < n; i++)
	{
	    int q = sc.nextInt();
	    int a = sc.nextInt();
	    int x = sc.nextInt();

	    calls[i] = new Call(q,a,x);
	}
	Arrays.sort(calls);

	int preQ = 0;
	int num = 0;
	int amount = 0;
	for(int i = 0; i < n; i++)
	{
	    if(calls[i].q != preQ)
	    {
	        preQ = calls[i].q;
		num = 0;
	    }
	    if(calls[i].a == 1)
	    {
		if(calls[i].x == 1)
		{
		    amount += 40;
		}else
		{
		    amount += 20;
		}
		amount += 10 * num;
		num++;

	    }else
	    {
		amount += 10;
	    }
	}
	System.out.println(amount);
    }
}

class Call implements Comparable< Call>
{
    int q;
    int a;
    int x;

    Call(int q, int a, int x)
    {
        this.q = q;
	this.a = a;
	this.x = x;
    }

    public int compareTo(Call other)
    {
        if(this.q < other.q)
	{
	    return -1;
	}else if(this.q == other.q)
	{
	    return 0;
	}else
	{
	    return 1;
	}
    }
}

  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯