Hexo
0%

对拍

发表于 更新于 分类于
学习对拍的笔记

参考笔记![http://note.youdao.com/s/NmNZruDo]

ZhengJie

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<iostream>
#include<algorithm>
using namespace std;

typedef struct HTnode
{
    int weight;
    int parent;
    int lchild;
    int rchild;
    bool operator == (HTnode& b) const
    {
        return (weight == b.weight);
        //return (lchild == b.lchild && parent == b.parent && rchild == b.rchild && weight == b.weight);
    }
}HTnode;

HTnode HuffmanTree[1000];
HTnode temp[1000];

int result[100];
int w[100];

bool cmp(HTnode a, HTnode b)
{
    return a.weight < b.weight;
}

void select(int begin, int end, int& s1, int& s2)
{
    HTnode temps1, temps2;
    for (int i = begin; i <= end; i++)
    {
        temp[i - begin] = HuffmanTree[i];
    }
    sort(temp, temp + (end - begin) + 1, cmp);
    temps1 = temp[0];
    temps2 = temp[1];
    int flag = 0;
    for (int i = begin; i <= end; i++)
    {
        if (temps1 == temps2)
        {
            if (HuffmanTree[i] == temps1 && flag == 0)
            {
                s1 = i;
                flag = 1;
            }
            else if (HuffmanTree[i] == temps2 && flag == 1)
                s2 = i;
        }
        else
        {
            if (HuffmanTree[i] == temps1)
            {
                s1 = i;
            }
            else if (HuffmanTree[i] == temps2)
                s2 = i;
        }
    }
}

void HuffmanCoding(int n)
{
    int s1 = 0, s2 = 0;
    int m = 2 * n - 1, i;
    for (i = 1; i <= n; i++)
    {
        HuffmanTree[i].weight = w[i];
    }
    for (i = n + 1; i <= m; i++)
    {
        select(1, i - 1, s1, s2);
        HuffmanTree[s1].parent = i;
        HuffmanTree[s2].parent = i;
        HuffmanTree[i].lchild = s1;
        HuffmanTree[i].rchild = s2;
        HuffmanTree[i].weight = HuffmanTree[s1].weight + HuffmanTree[s2].weight;
        HuffmanTree[s1].weight = 1e9;
        HuffmanTree[s2].weight = 1e9;
    }
}

void get_result(int n)
{
    for (int i = 1; i <= n; i++)
    {
        int start = 0;
        for (int c = i, f = HuffmanTree[i].parent; f != 0; c = f, f = HuffmanTree[f].parent)
        {
            if (HuffmanTree[f].lchild == c || HuffmanTree[f].rchild == c)
                ++start;
        }
        result[i] = w[i] * start;
    }
}

int main()
{
    //FILE* stream1;
    //freopen_s(&stream1, "data.in", "r", stdin);
    //freopen_s(&stream1, "ZhengJie.out", "w", stdout);//敲黑板！！！这里是对拍程序的输入重定向
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for (int i = 0; i <= 100; ++i) {
        HuffmanTree[i].weight = 0;
        HuffmanTree[i].lchild = 0;
        HuffmanTree[i].rchild = 0;
        HuffmanTree[i].parent = 0;
    }
    HuffmanCoding(n);
    /*for (int i = 1; i <= 2 * n - 1; i++)
    {
        cout << i << ":";
        show(HuffmanTree[i]);
    }*/
    get_result(n);
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += result[i];
        //cout << result[i] << endl;
    }
    cout << sum << endl;
    return 0;
}

BaoLi

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
#include<stdio.h>
#include<queue>
#include<vector>
#include<iostream>
using namespace std;

priority_queue<int, vector<int>, greater<int> >q;
int n, ans = 0;
int main()
{
 FILE* stream1;
 freopen_s(&stream1,"data.in", "r",stdin);
 freopen_s(&stream1,"BaoLi.out", "w", stdout);
 //scanf("%d", &n);
 cin >> n;
 while (n--)
 {
  int t;
  //scanf("%d", &t);
  cin >> t;
  q.push(t);
 }
 while (1)
 {
  int a = q.top();
  q.pop();
  if (q.empty())
   break;
  int b = q.top();
  q.pop();
  ans += a + b;
  q.push(a + b);
 }
 printf("%d\n", ans);
}

MAKEDATA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<Windows.h>
#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
 FILE* stream1;
 freopen_s(&stream1, "data.in", "w", stdout);
 srand(GetTickCount());
 int n = rand() % 30 + 1;
 cout << n << endl;
 for (int i = 1; i <= n; i++)
 {
  cout << rand() % 100 + 1 << " ";
 }
 cout << endl;
 return 0;
}

.bat

1
2
3
4
5
6
7
8
9
10
@echo off
set path=C:\Windows\System32
:loop
MakeData.exe
ZhengJie.exe
BaoLi.exe
fc ZhengJie.out BaoLi.out
if not errorlevel 1 goto loop
pause
goto loop