纪中集训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…差距!
———————华丽的分割线———————
言归正传
题目大意:
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!
上一篇: 程序环境和预处理C语言(三)
下一篇: CSS 知识点