欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

纪中集训2020.01.14【NOIP普及组】模拟赛C组总结——————【GDOI2003】求值

程序员文章站 2024-03-18 22:55:16
...

纪中集训2020.01.14【NOIP普及组】模拟赛C组总结

题目编号:(标题
Problem ID Title
0.【GDOI2003】求值
1.数制转换
2.小球
3.小明的游戏
巨佬估分:100+85.7+100+100=385.7
巨佬得分:100+0+80+40=220
蒟蒻得分:100+10+20+40=160
仅仅第5(似乎有点进步 ),一共20个人比赛FAQ
比赛完,巨佬们:啊!我少打了一点,少了个if,忘记附初始值了,差点就AK了!FAQ
蒟蒻们(其实就只有我一个 )这个好像真的不会呀!emmmm…差距!

———————华丽的分割线———————

言归正传

0.【GDOI2003】求值

题目大意:
Description
  给出N个整数X1,X2,X3,…,Xn,将这N个数从小到大排序为:A1,A2,A3,…,An,记数列A1,A2,A3,…,An的奇数项的和为P,偶数项之和为Q,令T=|P-Q|,计算T的值。

Input   输入文件的第一行为整数N(1<=N<=50000)。
  接下来的N行每行有一个整数,按顺序给出X1,X2,X3,。。。Xn的值(|Xi|<=1000)

Output   输出整数T的值。

Sample Input 3 1 3 2

Sample Output 2

分析一下:纯属模拟,真的模拟你们没有听错数据小,卡卡常数也许选择排序都能过去,qsort还是保险一点!最坏O(n^2),最快O(n log n)。注意:尽量用上位运算! 有2000ms!!!
上比赛时AC Pascal代码:

uses math;
var
        n,i:longint;
        x,y,ans:int64;
        a:array[0..1000005] of longint;
procedure qsort(l,r:longint);
var
        i,j,t,mid:longint;
begin
        i:=l;
        j:=r;
        mid:=a[(i+j) shr 1+1];
        repeat
                while a[i]<mid do
                begin
                        inc(i);
                end;
                while a[j]>mid do
                begin
                        dec(j);
                end;
                if i<=j then
                begin
                        t:=a[i];
                        a[i]:=a[j];
                        a[j]:=t;
                        inc(i);
                        dec(j);
                end;
        until i>j;
        if i<r then
        begin
                qsort(i,r);
        end;
        if j>l then
        begin
                qsort(l,j);
        end;
end;
begin
        readln(n);
        for i:=1 to n do
        begin
                read(a[i]);
        end;
        qsort(1,n);
        x:=0;
        y:=0;
        for i:=1 to n do
        begin
                if i mod 2=1 then
                begin
                        x:=x+a[i];
                end
                else if i mod 2=0 then
                begin
                        y:=y+a[i];
                end;
        end;
        ans:=abs(x-y);
        writeln(ans);
end.

附上比赛时的C++ AC 代码:

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,t,even,odd,ans;
int w[5000+20],fw[5000+20];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		if(x>=0)
			w[x]++;
		else
		{
			x=abs(x);
			fw[x]++;
		}
	}
	for(int i=1000;i>=1;i--)
	{
		while(fw[i]>=1)
		{
			
			t++;
			if(t%2!=0)
				odd+=i*(-1);
			else
				even+=i*(-1);
			fw[i]--;
		}
	}
	for(int i=0;i<=1000;i++)
	{
		while(w[i]>=1)
		{
			
			t++;
			if(t%2!=0)
				odd+=i;
			else
				even+=i;
			w[i]--;
		}
	}
	ans=abs(even-odd);
	printf("%d",ans);
	return 0;
}	

END!

下一题:纪中集训2020.01.14【NOIP普及组】模拟赛C组总结—————— 数制转换