codeforces 204 div.1

本文从WordPress迁移而来, 查看全部WordPress迁移文章

A.给出n,下面2n个实数,保证实数的输入,小数位都是3位。每次选取一个i,j(每个i,j只能被选一次,且i!=j,对i和j的大小无要求),将a[i]取下整,a[j]取上整,最后的结果就是2n个数字里面一半的数字取下整一半取上整,然后算一个绝对值 | (原本实数和) - (一半下整数和一半上整数的和) | , 使得绝对值最小

左式 = 实数和

右式 = 所有数字都取下整的和

绝对值 = | 左式 - 右式 |

显然右式是不符合要求的,还要将其中n个数字变为上整数。而原本的数字里面,其实只分了两类。

一类,将其从下整变为上整,数值是不变的(原本小数部分为0)

另一类,将其从下整变成上整,数值增加1(原本小数部分不为0),统计这类数字都多少个,COUNT

COUNT <= n的时候,最多只能选出COUNT个这类数字变为上整,至于具体选几个,枚举一次即可

COUNT > n的时候,至少要选出delta = COUNT-n个这类数字变为上整,必选之后,可选的余地,应该是n-delta个,具体还需要再选几个,枚举一次即可

其实就是,先全部取下整,那一些变为上整,一边变化,一边观察绝对值是否在一直变小,如果在某次变化过程中,绝对值反而越变越大了,那么就马上停止

因为输入数据保证小数3位,而输出也要保证小数3位,为了避免精度,整个程序都是转化为整数来处理的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 4010

struct NUM{
int a,b;
};
NUM a[N],sumL,sumR;
int n,COUNT;

int main(){
while(scanf("%d",&n)!=EOF){
char str[20];
sumL.a = sumL.b = 0;
sumR.a = sumR.b = 0;
COUNT = 0;
for(int i = 0; i < 2*n; i++){
scanf("%s",str);
sscanf(str,"%d.%d",&a[i].a,&a[i].b);
sumL.a += a[i].a; sumL.b += a[i].b;
sumR.a += a[i].a;
if(a[i].b != 0) COUNT++;
}
int valL = sumL.a * 1000 + sumL.b;
int valR = sumR.a * 1000;
if(COUNT > n){
int delta = COUNT - n;
valR += 1000 * delta;
COUNT = n - delta;
}
int absval = abs(valL - valR);
for(int i = 0; i < COUNT; i++){
valR += 1000;
int __absval = abs(valL - valR);
if(__absval >= absval) break;
absval = __absval;

}
if(absval < 1000) printf("0.%03d\n",absval);
else{
int INT = absval / 1000;
int REM = absval % 1000;
printf("%d.%03d\n",INT,REM);
}
}
return 0;
}

B: J会交换相邻的两个数字,但是F会投硬币,正面的话,他会交换一个逆序对(两个数字要相邻),反面的话,他会交换一个顺序对(两个数字要相邻),游戏的结束是整个序列变升序。J以最优策略交换,问在F的影响下,游戏结束的数学期望是多少

题解为,F投到正面和反面的概率相同,要么交换逆序对要么交换顺序对,其实F做的工作是相互抵消的,所以只需要考虑J的工作即可,J的任务就是以最优策略,每次交换一对相邻的数字,使序列变为升序,这个步数,其实就是逆序对;以前接触过这个结论差点忘记了,其实J交换的策略就是,先把最大的那个数字,一次次地轮换到最后的位置,然后把次大的数字一次次地轮换到次后的位置……最后把最小的数字换到了第一位,这里的步数就是序列的逆序对

然后,逆序对为偶数的话,ans = n 2,逆序对为奇数的话,ans = n 2-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 3010

int a[N],b[N],n,ANS;

void mersort(int L,int R,int *a,int *b){
if(L == R){
a[L] = b[L];
return ;
}
int mid = (L + R) >> 1;
mersort(L,mid,b,a);
mersort(mid+1,R,b,a);
int i = L,j = mid+1,k = L;
while(i <= mid && j <= R){
if(b[i] <= b[j]) a[k++] = b[i++];
else{
ANS += (mid - i + 1);
a[k++] = b[j++];
}
}
while(i <= mid) a[k++] = b[i++];
while(j <= R) a[k++] = b[j++];
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 0 ; i < n; i++){
scanf("%d",&a[i]);
b[i] = a[i];
}
ANS = 0;
mersort(0,n-1,a,b);
/*
printf("%d\n",ANS);
for(int i = 0; i < n; i++)
printf("%d ",a[i]);
puts("");
*/
if(ANS & 1) ANS += (ANS-1);
else ANS <<= 1;
printf("%d.000000\n",ANS);
}
return 0;
}

写了个暴力的程序,按照题意来模拟了一次,发现结果和答案是一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 3010
#define LIM 100000

int n,arr[N],a[N];
int hlist[N],tlist[N],lenh,lent;
bool Finished(){
for(int i = 1; i < n; i++)
if(a[i] < a[i-1]) return false;
return true;
}

int find(int m){
for(int i = 0 ; i < n; i++)
if(a[i] == m) return i;
return -1;
}

void Jeff(){
for(int number = n; number > 0; number--){
int index = find(number);
if(index != number-1){
swap(a[index],a[index+1]); return ;
}
}
}

void make_hlist(){
lenh = 0;
for(int i = 0 ; i < n-1; i++)
if(a[i] > a[i+1]) hlist[lenh++] = i;
}
void make_tlist(){
lent = 0;
for(int i = 0; i < n-1; i++)
if(a[i] < a[i+1]) tlist[lent++] = i;
}

void updata_head(){
int m = rand() % lenh;
int index = hlist[m];
swap(a[index],a[index+1]);
}
void updata_tail(){
int m = rand() % lent;
int index = tlist[m];
swap(a[index],a[index+1]);
}

void Furik(){
make_hlist();
make_tlist();
if(lenh == 0){}
else if(lent == 0){}
else{
int kind = rand() & 1;
if(kind == 0) updata_head();
else updata_tail();
}
}

int main(){
//freopen("input_B.txt","r",stdin);
//freopen("output_B.txt","w",stdout);

srand((int)time(0));
while(scanf("%d",&n)!=EOF){
for(int i = 0 ; i < n ;i++)
scanf("%d",&arr[i]);

double ave = 0;
for(int it = 0; it < LIM; it++){
int step = 0;
for(int i = 0; i < n; i++) a[i] = arr[i];
while(true){
if(Finished()) break;
Jeff();
step++;
if(Finished()) break;
Furik();
step++;
}
ave += step;
}
puts("");
printf("%.6lf\n",ave/LIM);
}
return 0;
}