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;
}