1 # include <cstdio>
 2 # include <algorithm>
 3 using namespace std;
 4 
 5 int main(){
 6     int n, a[10010];
 7     scanf("%d", &n);
 8     for(int i = 0; i < n; ++i)
 9         scanf("%d", a + i);
10     sort(a, a + n);
11     printf("%d", a[n/2]);
12     return 0;
13 }

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <algorithm>
 4 using namespace std;
 5 
 6 int main(){
 7     int n, t, * a, cur, ans = 0;
 8     scanf("%d %d", &n, &t);
 9     if(t < 0) t = -t;
10     a = new int[n+1];
11     for(int i = 0; i < n; ++i)
12         scanf("%d", a + i);
13     sort(a, a + n);
14     for(int i = 0; i < n; ){
15         cur = a[i];
16         for(int j = i + 1; j < n; ++j){
17             if(a[j] - cur == t){
18                 ans++;
19                 break;
20             }
21             else if(a[j] - cur > t)
22                 break;
23         }
24         for(i = i + 1 ; a[i] == cur && i < n; ++i);
25     }
26     printf("%d\n", ans);
27     delete [] a;
28     return 0;
29 }

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <algorithm>
 4 using namespace std;
 5 
 6 int n, a[100010];
 7 long long ans = 0;
 8 
 9 void Merge(int s, int m, int e){
10     int b[100010], i = s, j = m+1, k = s;
11     while(i <= m && j <= e){
12         if(a[i] >= a[j])    //如果相等，取a[i]，以保证稳定性
13             b[k++] = a[i++];
14         else{
15             b[k++] = a[j++];
16             ans += j - k;   //在位置j的选手超过了j-k个人，来到了位置k
17         }
18     }
19     while(i <= m) b[k++] = a[i++];
20     while(j <= e) b[k++] = a[j++];
21     for(k = s; k <= e; ++k)
22         a[k] = b[k];
23     return;
24 }
25 
26 void MergeSort(int s, int e){
27     if(s >= e) return;
28     int mid = (s + e) / 2;
29     MergeSort(s, mid);
30     MergeSort(mid + 1, e);
31     Merge(s, mid, e);
32     return;
33 }
34 
35 int main(){
36     scanf("%d", &n);
37     for(int i = 0; i < n; ++i)
38         scanf("%d", a + i);
39     MergeSort(0, n-1);
40     printf("%lld\n", ans);
41     return 0;
42 }

 1 # include <cstdio>
 2 # include <algorithm>
 3 using namespace std;
 4 
 5 typedef struct {
 6     int i, j, pea;
 7 } Point;
 8 
 9 bool cmp(Point p1, Point p2){
10     return p1.pea > p2.pea;
11 }
12 
13 int myabs(int num){
14     if(num < 0) return -num;
15     else return num;
16 }
17 
18 int T, M, N, K;
19 int cnt, ans;
20 Point p[2510];
21 
22 void Init(){
23     scanf("%d %d %d", &M, &N, &K);
24     cnt = 0;
25     ans = 0;
26     int pea;
27     for(int i = 0; i < M; ++i)
28         for(int j = 0; j < N; ++j){
29             scanf("%d", &pea);
30             //record points with peanuts > 0
31             if(pea){
32                 p[cnt].i = i;
33                 p[cnt].j = j;
34                 p[cnt].pea = pea;
35                 cnt++;
36             }
37         }
38 }
39 
40 void PickPeanut(){
41     //current: position [i][j], target p[cur]
42     //time: initially time = 1 (road to field)
43     int i = 0, j = p[0].j, cur = 0, time = 1;
44     while(cur < cnt && time <= K){
45         time += myabs(i - p[cur].i) + myabs(j - p[cur].j) + 1;
46         if(time + p[cur].i + 1 <= K)    //can fetch p[cur]
47             ans += p[cur].pea;
48         else
49             break;
50         i = p[cur].i;
51         j = p[cur].j;
52         ++cur;
53     }
54     return;
55 }
56 
57 int main(){
58     scanf("%d", &T);
59     while(T--){
60         Init();
61         sort(p, p + cnt, cmp);
62         PickPeanut();
63         printf("%d\n", ans);
64     }
65     return 0;
66 }

 1 # include <cstdio>
 2 # include <string.h>
 3 # include <algorithm>
 4 using namespace std;
 5 
 6 typedef struct{
 7     char s[55];
 8     int n;
 9 } String;
10 
11 bool cmp(String s1, String s2){
12     return s1.n < s2.n;
13 }
14 
15 String str[105];
16 char s[55];
17 int m, n;
18 
19 int Merge(int st, int mid, int end){
20     int i = st, j = mid + 1, k = st, ans = 0;
21     char s1[55];
22     while(i <= mid && j <= end){
23         if(s[i] <= s[j])
24             s1[k++] = s[i++];
25         else{
26             s1[k++] = s[j++];
27             ans += j-k;
28         }
29     }
30     while(i <= mid) s1[k++] = s[i++];
31     while(j <= end) s1[k++] = s[j++];
32     for(k = st; k <= end; ++k)
33         s[k] = s1[k];
34     return ans;
35 }
36 
37 int MergeSort(int st, int e){
38     if(st >= e) return 0;
39     int mid = (st + e) / 2;
40     return MergeSort(st, mid) + MergeSort(mid+1, e) + Merge(st, mid, e);
41 }
42 
43 int main(){
44     scanf("%d %d", &n, &m);
45     for(int i = 0; i < m; ++i){
46         scanf("%s", str[i].s);
47         strcpy(s, str[i].s);
48         str[i].n = MergeSort(0, n-1);
49     }
50     sort(str, str + m, cmp);
51     for(int i = 0; i < m; ++i)
52         printf("%s\n", str[i].s);
53     return 0;
54 }

 1 # include <iostream>
 2 using namespace std;
 3 
 4 int m, n, * heap, * num;
 5 
 6 void Init(){
 7     cin >> m >> n;
 8     heap = new int [n+1];
 9     num = new int [m+1];
10     for(int i=0; i<m; ++i)
11         cin >> num[i];
12     for(int i=0; i<n; ++i)
13         cin >> heap[i];
14 }
15 
16 void Exch(int i, int j){
17     int tmp = heap[i];
18     heap[i] = heap[j];
19     heap[j] = tmp;
20 }
21 
22 void ShiftDown(){
23     int cur = 0, s1 = 1, s2 = 2;
24     while(s2 < n){
25         if(heap[cur] <= heap[s1] && heap[cur] <= heap[s2])
26             return; //heap is min heap already
27         if(heap[s1] > heap[s2]){
28             Exch(cur, s2);
29             cur = s2;
30         }
31         else{
32             Exch(cur, s1);
33             cur = s1;
34         }
35         s1 = cur * 2 + 1;
36         s2 = s1 + 1;
37     }
38     if(s1 < n && heap[s1] < heap[cur])
39         Exch(cur, s1);
40     return;
41 }
42 
43 void Insert(){
44     //attention! n should > 0
45     for(int i=0; i<m && n; ++i){
46         cout << heap[0] << ‘ ‘;
47         if(num[i] >= heap[0])
48             heap[0] = num[i];
49         else
50             heap[0] = heap[--n];
51         ShiftDown();
52     }
53 }
54 
55 void Dele(){
56     delete [] heap;
57     delete [] num;
58 }
59 
60 int main(){
61     Init();
62     Insert();
63     Dele();
64     return 0;
65 }

 1 # include <iostream>
 2 using namespace std;
 3 
 4 struct LoserTree{
 5     int n;      // elements to be compared: n
 6     int LowExt; // lowest external elements number: LowExt
 7     int s;      // lowest internal level elements: s
 8     int offset; // total nodes numbers except lowest level
 9     int * tree; // loser tree
10     int * ele;  // elements to be compared
11     int winner(int c1, int c2);         // return winner index
12     int loser(int c1, int c2);          // return loser index
13     void init(int _n, int * _ele);      // initialize loser tree
14     void play(int p, int c1, int c2);   // compare ele[c1] & [c2], their parent is p
15     void build();   // rebuile loser tree
16     void print();   // print tree
17     void dele();    // delete tree
18 };
19 
20 int LoserTree::winner(int c1, int c2){
21     if(ele[c1] < ele[c2]) return c1;
22     else return c2;
23 }
24 
25 int LoserTree::loser(int c1, int c2){
26     if(ele[c1] < ele[c2]) return c2;
27     else return c1;
28 }
29 
30 void LoserTree::init(int _n, int * _ele){
31     ele = _ele;
32     n = _n;
33     tree = new int [n];
34     for(s = 1; s*2 < n; s *= 2);
35     offset = 2 * s - 1;
36     LowExt = 2 * (n - s);
37 }
38 
39 void LoserTree::play(int p, int c1, int c2){
40     int lastwin = winner(c1, c2), tempwin;
41     tree[p] = loser(c1, c2);
42     while(p > 1 && p % 2 == 1){ // right subtree goes up
43         tempwin = winner(lastwin, tree[p/2]);
44         tree[p/2] = loser(lastwin, tree[p/2]);
45         lastwin = tempwin;
46         p /= 2;
47     }
48     tree[p/2] = lastwin;    // p = 1, or tree[p] is a left sibling
49 }
50 
51 void LoserTree::build(){
52     int i;
53     // lowest level elements play
54     for(i = 2; i <= LowExt; i += 2)
55         play((offset+i)/2, i-1, i);
56     // one inner node vs one element
57     if(n % 2){
58         play(n/2, tree[n-1], LowExt+1);
59         i = LowExt + 3;
60     }
61     else i = LowExt + 2;
62     // the last second level elements play
63     for( ; i <= n; i += 2)
64         play((i-LowExt+n-1)/2, i-1, i);
65 }
66 
67 void LoserTree::print(){
68     for(int i = 0; i < n; ++i)
69         cout << ele[tree[i]] << ‘ ‘;
70     cout << endl;
71 }
72 
73 void LoserTree::dele(){
74     delete [] tree;
75 }
76 
77 int main(){
78     int n, m, * ele, index, val;
79     LoserTree MyTree;
80     cin >> n >> m;
81     ele = new int [n+2];
82     for(int i=1; i<=n; ++i)
83         cin >> ele[i];
84     MyTree.init(n, ele);
85     MyTree.build();
86     MyTree.print();
87     for(int i=0; i<m; ++i){
88         cin >> index >> val;
89         ele[index+1] = val; // change value if ele[index]
90         MyTree.build();     // rebuild
91         MyTree.print();
92     }
93     MyTree.dele();
94     delete [] ele;  // don‘t dorget!!!
95     return 0;
96 }