Counting the algorithms
--------------------------------------------------------------------------------
Time limit: 1sec. Submitted: 26
Memory limit: 64M Accepted: 3
Source : mostleg
--------------------------------------------------------------------------------
As most of the ACMers, wy's next target is algorithms, too. wy is clever, so he can learn most of the algorithms quickly. After a short time, he has learned a lot. One day, mostleg asked him that how many he had learned. That was really a hard problem, so wy wanted to change to count other things to distract mostleg's attention. The following problem will tell you what wy counted.
Given 2N integers in a line, in which each integer in the range from 1 to N will appear exactly twice. You job is to choose one integer each time and erase the two of its appearances and get a mark calculated by the differece of there position. For example, if the first 3 is in position 86 and the second 3 is in position 88, you can get 2 marks if you choose to erase 3 at this time. You should notice that after one turn of erasing, integers' positions may change, that is, vacant positions (without integer) in front of non-vacant positions is not allowed.
Input
There are multiply test cases. Each test case contains two lines.
The first line: one integer N(1 <= N <= 100000).
The second line: 2N integers. You can assume that each integer in [1,N] will appear just twice.
Output
One line for each test case, the maximum mark you can get.
Sample Input
3
1 2 3 1 2 3
3
1 2 3 3 2 1
Sample Output
6
9
Hint
We can explain the second sample as this. First, erase 1, you get 6-1=5 marks. Then erase 2, you get 4-1=3 marks. You may notice that in the beginning, the two 2s are at positions 2 and 5, but at this time, they are at positions 1 and 4. At last erase 3, you get 2-1=1 marks. Therefore, in total you get 5+3+1=9 and that is the best strategy.
先给一个数字N，接下来给出N个数，这n个数都在1-N之间，而且1-N这Ｎ个数每个都出现且只出现两次．
你的任务是，每次去掉一对数字，这对数字的位置绝对差当做你每去掉一对数字的得分，问你得分最多为多少。
其中，每去掉一对数字，位置是会变化的，以1 2 3 3 2 1来说，你去掉3这对，序列就变成1221，这么，2与2的位置绝对差就不再是原来的３而只有１了．
想求一个不高于o(n^2)的算法，还请大家多多帮忙，我写的是o(n^2)的算法。超时....
以下是我的代码：
#include <string.h>
int tmp1[1024],tmp2[1024];
int differ[1024];
int a[2048];
bool isVisited[1024];
int main()
{
int sum=0,i,j,n;
while(scanf("%d",&n)!=EOF)
{
sum=0;
n*=2;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(tmp1[a[i]]==0)
tmp1[a[i]]=i;
else
{
tmp2[a[i]]=i;
differ[a[i]]=tmp2[a[i]]-tmp1[a[i]];
}
}
for(i=1;i<=n;i++)
{
if(!isVisited[a[i]])
{
sum+=differ[a[i]];
for(j=tmp2[a[i]]+1;j<=n;j++)
{
if(tmp1[a[j]]>tmp2[a[i]]);
else differ[a[j]]--;
}
}
isVisited[a[i]]=true;
}
printf("%d\n",sum);
memset(tmp1,0,sizeof(tmp1));
memset(isVisited,false,sizeof(isVisited));
}
return 0;
}
