萌喵小窝

发表于

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

发表于 更新于 分类于

Given a singly linked list, you are supposed to rearrange its elements so that all the negative values appear before all of the non-negatives, and all the values in [0, K] appear before all those greater than K. The order of the elements inside each class must not be changed. For example, given the list being 18→7→-4→0→5→-6→10→11→-2 and K being 10, you must output -4→-6→-2→7→0→5→10→18→11.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=1000). The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1. Then N lines follow, each describes a node in the format: Address Data Next where Address is the position of the node, Data is an integer in [-105, 105], and Next is the position of the next node. It is guaranteed that the list is not empty.

Output Specification:

For each case, output in order (from beginning to the end of the list) the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

Sample Output:

33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

把链表分成三个部分，小于的一部分，大于0小于等于k的一部分，大于k的一部分。 和前面集体LinkList的处理方式相同，采用5位数的数组来定位数组的地址。

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 <cstdio>
#include <vector>

using namespace std;

struct node {
    int first, value, next;
};

vector<node> neg, lesser, greater;

void spit(node *nodes, int first, int k) {
    while (first != -1) {
        if (nodes[first].value < 0) {
            neg.push_back(nodes[first]);
        } else if (nodes[first].value <= k) {
            lesser.push_back(nodes[first]);
        } else {
            greater.push_back(nodes[first]);
        }
        first = nodes[first].next;
    }
}

vector<node> ans;

void merge() {
    ans = neg;
    for (int i = 0; i < lesser.size(); i++) {
        ans.push_back(lesser[i]);
    }
    for (int i = 0; i < greater.size(); i++) {
        ans.push_back(greater[i]);
    }
}

void printAns() {
    int i = 0;
    for (; i < ans.size() - 1; i++) {
        printf("%05d %d %05d\n", ans[i].first, ans[i].value, ans[i + 1].first);
    }
    printf("%05d %d -1\n", ans[i].first, ans[i].value);
}

int main() {
    int first = 0, n = 0, k = 0, temp = 0;
    scanf("%d %d %d", &first, &n, &k);
    node nodes[100000];
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp);
        scanf("%d %d", &nodes[temp].value, &nodes[temp].next);
        nodes[temp].first = temp;
    }
    spit(nodes, first, k);
    merge();
    printAns();

    return 0;

}

发表于 更新于 分类于

Given a sequence of positive integers and another positive integer p. The sequence is said to be a “perfect sequence” if M <= m * p where M and m are the maximum and minimum numbers in the sequence, respectively. Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (<= 105) is the number of integers in the sequence, and p (<= 109) is the parameter. In the second line there are N positive integers, each is no greater than 109.

Output Specification:

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input:

10 8
2 3 20 4 5 1 6 7 8 9

Sample Output:

8

方法：快速排序 + 二分查找 tips：M <= m * p 最好转化成 M / p <= m

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
#include <cstdlib>
#include <cstdio>

int get(int *nums, double x, int l, int r) {
    int mid = (l + r) / 2;
    if (l >= r) return mid;
    if (nums[mid] < x) return get(nums, x, mid + 1, r);
    if (nums[mid] - x < 0.1) return mid;
    else return get(nums, x, l, mid);
}

int cmp(const void *a, const void *b) {
    int arg1 = *static_cast<const int *>(a);
    int arg2 = *static_cast<const int *>(b);

    if (arg1 > arg2) return 1;
    if (arg1 < arg2) return -1;
    return 0;
}

int main() {
    int n = 0, p = 0;
    scanf("%d %d", &n, &p);
    int *nums = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    qsort(nums, n, sizeof(nums[0]), cmp);
    int cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        int j = get(nums, nums[i] * 1.0 / p, 0, i);
        cnt = i - j + 1 > cnt ? i - j + 1 : cnt;
    }
    printf("%d\n", cnt);
    delete[] nums;
    return 0;
}
0%