本文从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); 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 () { 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 ; }