基础算法(一)

 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

#include <iostream>
using namespace std;

const int N = 1000010;
int a[N];

void quicksort(int a[], int l, int r){
    if (l >= r) return;
    
    int i = l-1, j = r+1, x = a[(l+r)>>1];
    while (i < j){
        do i ++ ; while (a[i] < x);
        do j -- ; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    quicksort(a, l, j);
    quicksort(a, j+1, r);
}

int main(){
    int n;
    cin >> n;
    for(int i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }
    
    quicksort(a, 0, n-1);
    
    for(int i=0; i<n; i++) printf("%d ", a[i]);
    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

#include <iostream>
using namespace std;

const int N = 1000010;
int a[N];

int quicksort(int a[], int l, int r, int k){
    if (l >= r){
        return a[l];
    }
    
    int i = l-1, j = r+1, x = a[(l+r)>>1];
    while (i < j)
    {
        do i ++ ; while (a[i] < x);
        do j -- ; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    if (j - l + 1 >= k){
        return quicksort(a, l, j, k);
    }
    else return quicksort(a, j + 1, r, k - (j - l + 1));
}

int main(){
    int n, k;
    cin >> n >> k;
    for(int i=0; i<n; i++) cin >> a[i];
    
    cout << quicksort(a, 0, n-1, k) << endl;
    
    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

#include <iostream>
using namespace std;

const int N = 1e6 + 10;

int a[N], tmp[N];

void merge_sort(int q[], int l, int r){
    if (l >= r) return;

    int mid = l + r >> 1;

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
    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

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
int a[N];
int nums;
unsigned long result = 0;

void merge_sort(int a[], int l, int r){
    if (l >= r) return;
    int mid = (l+r) >> 1;
    
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    
    int temp[r - l + 1];
    int lptr = l;
    int rptr = mid + 1;
    int tempptr = 0;
    while(lptr <= mid && rptr <= r){
        if(a[lptr] <= a[rptr]) temp[tempptr++] = a[lptr++];
        else {
            temp[tempptr++] = a[rptr++];
            result += (mid - lptr + 1);
        } 
    } 
    while (lptr <= mid) temp[tempptr++] = a[lptr++];
    while (rptr <= r) temp[tempptr++] = a[rptr++];
    
    for (int i = l, j = 0; i <= r; i ++, j ++){
        a[i] = temp[j];
    }
}

int main(){
    scanf("%d", &nums);
    for(int i = 0; i < nums; i++) scanf("%d", &a[i]);

    merge_sort(a, 0, nums-1);
    cout << result;
    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

#include <iostream>
using namespace std;

const int maxn = 100005;

int n, q, x, a[maxn];

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++)    scanf("%d", &a[i]);
    while (q--) {
        scanf("%d", &x);
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] < x) l = mid + 1;
            else r = mid;
        }
        if (a[l] != x) {
            printf("-1 -1\n");
            continue;
        }
        int l1 = l, r1 = n;
        while (l1 + 1 < r1) {
            int mid = l1 + r1 >> 1;
            if (a[mid] <= x) l1 = mid;
            else r1 = mid;
        }
        printf("%d %d\n", l, l1);
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include<iostream>
using namespace std;

double n,l,r,mid;

double q(double a){return a*a*a;}
int main(){
    cin >> n;
    l=-100, r=100;
    while(r - l >= 1e-7){
        mid=(l+r)/2;
        if (q(mid)>=n) r=mid;
        else l=mid;
    }
    printf("%.06f", l);
    return 0;
}