解题报告

http://www.spoj.pl/problems/NWERC11E/

题目：Please, go first

You are currently on a skiing trip with a group of friends. In general, it is going well: you enjoy the skiing during the day and, of course, the après-skiing during the night. However, there is one nuisance: the skiing lift. As always, it is too small, and can only serve one person every 5 seconds. To make matters worse, you and your friends generally don’t arrive simultaneously at the lift, which means that you spend time waiting at the bottom of the mountain for the lift and at the top again for your friends.

The waiting at the top is especially inefficient. In fact, you realize that if your friends haven’t arrived yet, you might as well let other people pass you in the queue. For you, it makes no difference, since otherwise you’d be waiting at the top. On the other hand, your actions might save them time if their friends have already arrived and are currently waiting for them at the top.

You are wondering how much time would be saved if everybody adopts this nice attitude. You have carefully observed the queue for a while and noticed which persons form groups of friends. Suppose someone lets another pass if doing this doesn’t change his own total waiting time, but saves time for the other person. Do this over and over again until it can’t be done anymore. How much time will this save, in total?

Input

On the first line a positive integer: the number of test cases, at most 100. After that per test case:

• one line with an integer n (1 ≤ n ≤ 25 000): the number of people in the line for the lift.

• one line with n alphanumeric characters (uppercase and lowercase letters and numbers): the queue. The first person in this line corresponds to the person at the head of the queue. Equal characters correspond to persons from the same group of friends.

Output

Per test case:

• one line with an integer: the time saved, in seconds.

Sample in- and output

Input Output

2

6

AABABB

10

Ab9AAb2bC2 15

45

Copyright notice

This problem text is copyright by the NWERC 2011 jury. It is licensed under the Creative Commons Attribution-Share Alike license version 3.0; The complete license text can be found at: http://creativecommons.org/licenses/by-sa/3.0/legalcode

题目大意：这道题目是关于排序的问题，朋友之间的等待，意味着在朋友中要以最后一个人为准，所以，每组人都要等待的最后一个最后一个朋友的到来，正好可以发扬传统美德，在不增加自己的等待时间的同时可以给别人让时间

代码：

#include

int main()

{

int n,i,j,c,k,l,s;

char z[25001],d[25001];

int a[25001],b[25001];

scanf("%d",&n); // 有N组数据

while(n–)

{

scanf("%d",&c); // 每组数据有C个字符组成

getchar();

s=0;

gets(z); // Z为字符串

for(i=0;i

b[i]=0;

a[i]=0;

}

k=0;

for(i=c-1;i>=0;i–) // 从后向前倒着比较

{

for(j=c-1;j>i;j–)

if(z[i]==z[j])

break;

if(j==i)

{

a[k]=i+1;

d[k]=z[i];

k++;

for(l=0;l

b[k-1]++;

}

}

for(i=k-1;i>=0;i–)

{

s+=(a[i]-b[i])*b[i]*5;

b[i-1]+=b[i];

}

printf("%d\n",s);

}

return 0;

}