Welcome to BeckoninGshy's Bolg

LeetCode-394-字符串解码

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:
1
2
3
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

Solution1（递归法）：

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
class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        string ans = "";
        while(i < s.size()){
            ans += dfs(s,i);
        }
        return ans;
    }
    string dfs(string s, int &i){
        int num = 0,flag = 0;
        string t = "", tt = "";
        while(i < s.size() && s[i] >= '0' && s[i] <= '9'){
            num = num * 10 + (s[i]-'0');
            i++;
        }
        if(i < s.size() && s[i] == '[') flag = 1, i++;
        while(i < s.size() && s[i] != ']'){
            if(s[i] >= '0' && s[i] <= '9'){
                t += dfs(s,i);
                continue;
            }
            t += s[i];
            i++;
        }
        if(t.size() > 0){
            tt = t;
            while(--num > 0) tt += t;
        }
        if(i < s.size() && s[i] == ']') i++;
        return tt;
    }
};

思路：

很正常的思路就是递归，每遇到数字就递归到下一层，等下一层的结束后，返回到当前层接着处理，在遇到’]’或者走到最后时，结束这一层的处理。

Solution2（栈）：

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
class Solution {
public:
    string decodeString(string s) {
        stack<int> numstk;
        stack<string> strstk;
        int num = 0;
        string cur = ""; //当前层可以形成的串
        for(int i = 0; i < s.size(); i++){
            if(s[i] >= '0' && s[i] <= '9'){
                num = num * 10 + (s[i]-'0');
            }else if(s[i] == '['){
                //模拟递归，该去下一层了。
                numstk.push(num);
                strstk.push(cur);
                num = 0;
                cur = "";
            }else if(s[i] == ']'){
                //这一层已经完成处理
                for(int j = 0; j < numstk.top(); j++){
                    strstk.top() += cur;  
                }
                //返回上一层
                cur = strstk.top();
                strstk.pop();
                numstk.pop();
            }else{
                cur += s[i];
            }
        }
        return cur;
    }
};

思路：

使用栈就是为了能保留当前层的信息，这里的进入下一层的时机和递归版略有差别，在到达’[‘的时候才进入下一层，主要是为了确定num的值和保存之前正处理的串的信息，在’]’的时候要处理完当前层，并且返回上一层。

阅读更多
LeetCode-117-填充每个节点的下一个右侧节点指-II

117. 填充每个节点的下一个右侧节点指针 II

此题为116. 填充每个节点的下一个右侧节点指针的进阶版本。

给定一个二叉树

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

1
2
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]

提示：

  • 树中的节点数小于 6000
  • 100 <= node.val <= 100

Solution1（迭代版）：

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
class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return NULL;
        Node* head = root;
        Node* pre = NULL;
        while(root){
            Node* sub = NULL;
            while(pre){
                if(pre->left){
                    if(sub) sub->next = pre->left;
                    sub = pre->left;
                }
                if(pre->right){
                    if(sub) sub->next = pre->right;
                    sub = pre->right;
                }
                pre = pre->next;
            }
            pre = root;
            while(root){
                if(root->left){
                    root = root->left;
                    break;
                } else if(root->right){
                    root = root->right;
                    break;
                } else {
                    root = root->next;
                }
            }
        }
        return head;
    }
};

思路：

与上一题类似，先设置下父指针，找到父指针下所有存在的结点相连接，然后找到下一层的第一个结点，将其继续当做父节点。

Solution2（递归版）：

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

class Solution {
public:
    Node* connect(Node* root) {
        
        if(!root || (!root->left && !root->right)) return root;
        //先把当前结点连接
        if(root->left && root->right) root->left->next = root->right;
        Node* sub = root->right ? root->right : root->left;
        //跳过没有子节点的节点
        Node* head = root->next;
        while(head && !head->left && !head->right){
            head = head->next;
        }
        sub->next = head ? (head->left ? head->left : head->right) : NULL;
        connect(root->right);
        connect(root->left);
        return root;
    }
};

思路：

如果是叶子节点或空节点，则直接返回。
如果有两个子节点，先把两节点之间连接，把右节点当做下一层要操作的节点。
如果只有一个子节点，把该节点当做下一层要操作的节点。

将下一层的节点连接（寻找当前层的非叶子结点，将它的子节点与该结点的下一层节点连接）。

这里注意一定要先构建右子树，再构建左子树，因为寻找父节点的兄弟节点是从左到右遍历的，如果右子树未构建好就遍历，则会出错。
阅读更多
LeetCode-116-填充每个节点的下一个右侧节点指针

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

Solution1（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return NULL;
        Node* l = root->left;
        Node* r = root->right;
        while(l){
            l->next = r;
            l = l->right;
            r = r->left;
        }
        connect(root->left);
        connect(root->right);
        return root;
    }
};

Solution2（迭代版）：

一层一层的考虑，由于每个结点往后连需要用到其父节点的信息，所以我们可以在下一层结点的next指针连接完毕后，在往下一层移动时，父结点就可以利用已经连接好的next指针进行平滑的向右移动了。这样直到最后一层结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
// Definition for a Node.

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        Node* pre = NULL;
        Node* cur = root;
        while(cur){
            while(pre){
                pre->left->next = pre->right;
                if(pre->next){
                    pre->right->next = pre->next->left;
                }
                pre = pre->next;
            }
            pre = cur;
            cur = cur->left;
        }
        return root;
    }
};
阅读更多
01背包问题详解
DP 背包问题

01背包

题目描述：

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

阅读更多
背包九讲
DP 背包问题

01背包

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

阅读更多
POJ-3614-Sunscreen

POJ-3614-Sunscreen

题目描述：

To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they’re at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn’t tan at all……..

The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPFi (1 ≤ SPFi ≤ 1,000). Lotion bottle i can cover coveri cows with lotion. A cow may lotion from only one bottle.

What is the maximum number of cows that can protect themselves while tanning given the available lotions?

输入：

  • Line 1: Two space-separated integers: C and L

  • Lines 2..C+1: Line i describes cow i’s lotion requires with two integers: minSPFi and maxSPFi

  • Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri

输出：

A single line with an integer that is the maximum number of cows that can be protected while tanning

输入示例：

1
2
3
4
5
6
3 2
3 10
2 5
1 5
6 2
4 1

输出示例：

1
2

题目大意：

有C头牛，每个牛Ci在一个给定的区间上需要涂防晒霜，有L种防晒霜，给出每个防晒霜适合的数值SPF[i]和个数cover[i]，求能最多满足牛的个数。

贪心策略：

按区间的开始位置递减排序，依次考虑每头牛。
对于每头牛，选取满足在此区间内最大的防晒霜。

Solution1（暴力版）：

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
#include<iostream>
#include<utility>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int MAXN = 5000+10;
int C,L;
PII p[MAXN];
PII q[MAXN];
int main(){
    int ans = 0;
    scanf("%d%d",&C,&L);
    for(int i = 0; i < C; i++){
        scanf("%d%d",&p[i].first,&p[i].second);
    }
    sort(p,p+C);
    for(int i = 0; i < L; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        q[i].first = a;
        q[i].second = b;
    }
    sort(q,q+L);
	//从开始位置大到小考察每头牛。
    for(int i = C-1; i >= 0; i--){
		//同样，对于每头牛，考察在该牛区间内最右的防晒霜。
        for(int j = L-1; j >= 0; j--){
            if(q[j].second > 0 && q[j].first >= p[i].first && q[j].first <= p[i].second){
                ans++;
                q[j].second--;
                break;
            }
        }
    }
    printf("%d",ans);
    return 0;
}

Solution2（平衡树版）：

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>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int MAXN = 2510;
typedef pair<int,int> PII;
int N,M;
PII cows[MAXN];
int main(){
    cin >> N >>M;
    for(int i = 0; i < N; i++){
        cin >> cows[i].first >> cows[i].second;
    }
    sort(cows,cows+N);
    map<int,int> spfa;
    for(int i = 0; i < M; i++){
        int spa,cover;
        cin >> spa >> cover;
        spfa[spa] += cover;
    }
    spfa[0] = spfa[1001] = N;
    int ans = 0;
    for(int i = N-1; i >= 0; i--){
        map<int,int>::iterator it = spfa.upper_bound(cows[i].second);
        --it;
        if(cows[i].first <= it->first && cows[i].second >= it->first){
            ans++;
            if(-- it->second == 0) spfa.erase(it);
        }
    }
    cout << ans;
    return 0;
}
阅读更多
AcWin-135-最大子序和

AcWing 135. 最大子序和

题目描述

输入一个长度为n的整数序列，从中找出一段长度不超过m的连续子序列，使得子序列中所有数的和最大。

输入格式
第一行输入两个整数n,m。

第二行输入n个数，代表长度为n的整数序列。

同一行数之间用空格隔开。

输出格式
输出一个整数，代表该序列的最大子序和。

数据范围
1≤n,m≤300000

样例

1
2
3
4
5
输入样例：
6 4
1 -3 5 1 -2 3
输出样例：
7

思路：

求一个区间长度为M的序列和可以用前缀和相减的形式来得到：

1
k = sum[i]- sum[i-M]

而要求当前区间P内的最大值，可以找到该区间（sum[i-1]–sum[i-m]）内的最小值，用sum[i]减去该值，得到以sum[i]为终点的区间的最大值，对于每个区间，都求得一个最大值，再到这些之内取最大即为答案。

所以现在的问题变为：给定一个区间，如何找出给区间内的最小值。

如果暴力求，会使总的复杂度为O(N2)，不符合要求。
再看一下要解决的问题，我们想到使用单调队列，可以在线求出一组序列的最值，所以我们使用一个大小为M的队列来维护最值。

这样总的复杂度就为线性的了。

C++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
#include<deque>
#include<cstdio>
using namespace std;
const int MAXN = 1e6+10;
long long a[MAXN],sum[MAXN],ans = -1e10;

int main(){
    deque<int> q;
    int N,M;
    cin >> N >> M;
    for(int i = 0; i < N; i++) cin >> a[i];
    for(int i = 1; i <= N; i++) sum[i] = sum[i-1] + a[i-1]; //前缀和
    for(int i = 1; i <= N; i++){
        while(q.size() && q.front() < i - M) q.pop_front(); //超出窗口范围，清除
        ans = max(ans, sum[i]-sum[q.front()]); //更新值
        while(q.size() && sum[q.back()] > sum[i]) q.pop_back(); //维护单调性质
        q.push_back(i);
    }
    cout << ans;
    return 0;
}
阅读更多
POJ-Telephon-Lines(二分+最短路)

POJ-Telephone Lines

题目描述：

Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.

There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John’s property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart.

The i-th cable can connect the two distinct poles Ai and Bi, with length Li (1 ≤ Li ≤ 1,000,000) units if used. The input data set never names any {Ai, Bi} pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.

As it turns out, the phone company is willing to provide Farmer John with K (0 ≤ K < N) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.

Determine the minimum amount that Farmer John must pay.

输入：

  • Line 1: Three space-separated integers: N, P, and K
  • Lines 2..P+1: Line i+1 contains the three space-separated integers: Ai, Bi, and Li

输出：

  • Line 1: A single integer, the minimum amount Farmer John can pay. If it is impossible to connect the farm to the phone company, print -1.

输入示例：

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

输出示例：

1
4

题目大意：

一电话公司要链接编号1和N的电话，中间可能需要架设多条电话线，线缆厂商可以免费给电话公司铺设k条电缆，超过k条之后，要按其余的线缆中最长的进行相应收费费用与长度相同，求电话公司需要付的最小费用。

思路：

其实就是求无向图中，从1到N中，使最多可以“宽恕”k条最长边之后最长的边的长度尽可能小的路径。

单独求这样一个问题好像很复杂，我们稍加分析发现，答案一定在给定的边长、零或者不存在这样的路径这三种情况中，我们先假定一个答案，用这个答案去试探从1-N的路径有没有符合条件的。

具体的判断就是求一条大于答案的边长数最小的一条路径。可以使用最短路来求，松弛条件根据到当前边的超过答案的数量中选择更小的一条边。我们最后判断到达N后其数量是否超过k，就能判断这是否是一条符合条件的边。

然后将存放所有可能是答案的数组排序后进行二分。

这里求“最短路”用了两个最短路模板：

Solution1（Dijkstra）：

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
/*
 * @Date: 2019-10-07 18:55:30
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-10-08 22:59:49
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 10000+10;
const int INF = 0x3f3f3f3f;
int n,p,k;
struct node{
    int b,ca;
    node(int _b,int _ca):b(_b),ca(_ca){}
    node(){}
    bool operator<(const node &q)const{
        return ca > q.ca;
    }
};
vector<node> V[MAXN];
int dis[MAXN]; //dis存超过目标值x的电话线条数。
int vis[MAXN];
int cost[MAXN];
int Dijkstra(int x){
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1] = 0;
    priority_queue<node> q;
    q.push(node(1,dis[1]));
    node temp;
    while(!q.empty()){
        temp = q.top(); q.pop();
        int u = temp.b;
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = 0; i < V[u].size(); i++){
            int v = V[u][i].b;
            int c = V[u][i].ca;
            c = c > x ? 1 : 0;
            //更新到当前结点的超过x的条数
            if(!vis[v] && dis[v] > dis[u] + c){
                
                dis[v] = dis[u] + c;
                q.push(node(v,dis[v]));
            }
        }
    }
    //是
    return dis[n]<= k;
}




int main(){
    freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&p,&k);
    for(int i = 0; i < p; i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        V[a].push_back(node(b,c));
        V[b].push_back(node(a,c));
        cost[i+1] = c; 
    }
    //按长度进行二分，根据超过该长度的个数是否超过k来确定边界。
    sort(cost+1,cost+1+p);
    if(!Dijkstra(cost[p])){
        printf("-1\\n");
        return 0;
    }
    //答案有可能是0，所以从0开始。
    int l = 0, r = p-1;
    while(l < r){
        int mid = l+r>>1;
        if(Dijkstra(cost[mid])) r = mid;
        else l = mid+1;
    }
    printf("%d",cost[l]);
    return 0;
}

Solution2（SPFA）：

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
/*
 * @Date: 2019-10-07 18:55:30
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-10-09 19:32:17
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 10000+10;
const int INF = 0x3f3f3f3f;
int n,p,k;
struct node{
    int b,ca;
    node(int _b,int _ca):b(_b),ca(_ca){}
    node(){}
    bool operator<(const node &q)const{
        return ca > q.ca;
    }
};
vector<node> V[MAXN];
int dis[MAXN]; //dis存超过目标值x的电话线条数。
int vis[MAXN];
int inq[MAXN];
int cost[MAXN];
int SPFA(int x){
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(inq,0,sizeof(inq));
    
    dis[1] = 0;
    queue<int> q;
    q.push(1);
    node temp;
    inq[1] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        inq[u] = false;
        for(int i = 0; i < V[u].size(); i++){
            int v = V[u][i].b;
            int c = V[u][i].ca;
            c = c > x ? 1 : 0;
            //更新到当前结点的超过x的条数
            if(dis[v] > dis[u] + c){
                
                dis[v] = dis[u] + c;
                if(!inq[v]){
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
    //是
    return dis[n]<= k;
}




int main(){
    freopen("in.txt","r",stdin);
    scanf("%d%d%d",&n,&p,&k);
    for(int i = 0; i < p; i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        V[a].push_back(node(b,c));
        V[b].push_back(node(a,c));
        cost[i+1] = c; 
    }
    //按长度进行二分，根据超过该长度的个数是否超过k来确定边界。
    sort(cost+1,cost+1+p);
    if(!SPFA(cost[p])){
        printf("-1\\n");
        return 0;
    }
    //答案有可能是0，所以从0开始。
    int l = 0, r = p-1;
    while(l < r){
        int mid = l+r>>1;
        if(SPFA(cost[mid])) r = mid;
        else l = mid+1;
    }
    printf("%d",cost[l]);
    return 0;
}
阅读更多
POJ-2010-Mo-Universit--Financia-Aid（优先队列或二分）

POJ-2010-Moo University - Financial Aid

题目描述：

Bessie noted that although humans have many universities they can attend, cows have none. To remedy this problem, she and her fellow cows formed a new university called The University of Wisconsin-Farmside,”Moo U” for short.

Not wishing to admit dumber-than-average cows, the founders created an incredibly precise admission exam called the Cow Scholastic Aptitude Test (CSAT) that yields scores in the range 1..2,000,000,000.

Moo U is very expensive to attend; not all calves can afford it.In fact, most calves need some sort of financial aid (0 <= aid <=100,000). The government does not provide scholarships to calves,so all the money must come from the university’s limited fund (whose total money is F, 0 <= F <= 2,000,000,000).

Worse still, Moo U only has classrooms for an odd number N (1 <= N <= 19,999) of the C (N <= C <= 100,000) calves who have applied.Bessie wants to admit exactly N calves in order to maximize educational opportunity. She still wants the median CSAT score of the admitted calves to be as high as possible.

Recall that the median of a set of integers whose size is odd is the middle value when they are sorted. For example, the median of the set {3, 8, 9, 7, 5} is 7, as there are exactly two values above 7 and exactly two values below it.

Given the score and required financial aid for each calf that applies, the total number of calves to accept, and the total amount of money Bessie has for financial aid, determine the maximum median score Bessie can obtain by carefully admitting an optimal set of calves.

输入：

  • Line 1: Three space-separated integers N, C, and F

  • Lines 2..C+1: Two space-separated integers per line. The first is the calf’s CSAT score; the second integer is the required amount of financial aid the calf needs

输出：

  • Line 1: A single integer, the maximum median score that Bessie can achieve. If there is insufficient money to admit N calves,output -1.

输入示例：

1
2
3
4
5
6
3 5 70
30 25
50 21
20 20
5 18
35 30

输出示例：

1
35

提示：

Sample output:If Bessie accepts the calves with CSAT scores of 5, 35, and 50, the median is 35. The total financial aid required is 18 + 30 + 21 = 69 <= 70.

题目大意：

奶牛大学招收N名学生（奇数），有C名候选学生，该大学可以承受最多F的贷款，求能招收的学生中，中位数尽可能的大，如果没有满足条件的学生，输出-1。

思路1（优先队列）：

以学生成绩排序，然后以每个学生为中位数，寻找比他成绩低的学生中尽可能贷款少的N/2个学生，和比他成绩高的学生中尽可能贷款少的N/2个学生。结果就是满足:

1
aid：cur_i+lower_i+upper_i <= F

中最大的那个。

难度就是如何保持尽可能少的贷款。

这里选择维持一个长度始终为N/2长度的优先队列。

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
/*
 * @Date: 2019-10-06 17:36:17
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-10-07 16:04:57
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<utility>
using namespace std;
const int MAXN = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;

PII arr[MAXN];
int M,N,S;
int lowa[MAXN],upa[MAXN];


int main(){
    freopen("in.txt","r",stdin);
    scanf("%d%d%d",&M,&N,&S);
    for(int i = 0; i < N; i++){
        scanf("%d%d",&arr[i].first,&arr[i].second);
    }
    int half = M/2;
    sort(arr,arr+N);
    memset(lowa,INF,sizeof(lowa));
    memset(upa,INF,sizeof(upa));
    priority_queue<int> q;
    //确定以每个人为中位数， 比自己分数低的人的最小aid总和
    int total = 0;
    for(int i = 0; i < N; i++){
        if(q.size() == half) lowa[i] = total;
        total += arr[i].second;
        q.push(arr[i].second);
        if(q.size() > half){
            total -= q.top();
            q.pop();
        }
    }
    while(q.size()) q.pop();
    total = 0;
    //确定以每个人为中位数， 比自己分数高的人的最小aid总和
    for(int i = N-1; i >= 0; i--){
        if(q.size() == half) upa[i] = total;
        q.push(arr[i].second);
        total += arr[i].second;
        if(q.size() > half){
            total -= q.top();
            q.pop();
        }
    }
    int ans = -1;
    //从后往前寻找第一个满足条件的
    for(int i = N-1; i >= 0; i--){
        if(arr[i].second + lowa[i] + upa[i] <= S) {ans = arr[i].first;break;}
    }
    printf("%d\\n",ans);
    return 0;
}

思路2（二分）：

先对成绩排序，按成绩进行二分，对是否满足是中位数和sum <= F两个性质进行判断。

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
/*
 * @Date: 2019-10-06 17:36:17
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-10-07 17:18:16
 */

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<utility>
using namespace std;
const int MAXN = 1e5+10;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;

struct cow{
    int csat,aid;
    bool operator <(const cow &q)const{
        if(csat == q.csat) return aid < q.aid;
        return csat < q.csat;
    }
}cows[MAXN];
struct n{
    int index,aid;
    bool operator <(const n &q)const{
        return aid < q.aid;
    }
}node[MAXN];
int M,N,S,half,ans = -1;
int aid[MAXN];

int check(int x){
    int l = 0, r = 0, sum = cows[x].aid;
    for(int i = 0; i < N; i++){
        //在原位置的左边，且符合规定
        if(l < half && node[i].index < x && sum + node[i].aid <= S){
            l++;
            sum += node[i].aid;
        //在原位置的右边，且符合规定
        }else if(r < half && node[i].index > x && sum + node[i].aid <= S){
            r++;
            sum += node[i].aid;
        }
    }
    //都到不了half，说明无法满足小于等于S。
    if(l < half && r < half) return -1;
    if(l < half) return 1;
    else if(r < half) return 0;
    //l = r = half 找到了一个符合条件的，更新答案，继续寻找后面。
    ans = cows[x].csat;
    return 1;
    
}

int main(){
    freopen("in.txt","r",stdin);
    scanf("%d%d%d",&M,&N,&S);
    for(int i = 0; i < N; i++){
        scanf("%d%d",&cows[i].csat,&cows[i].aid);
    }
    half = M/2;
    sort(cows,cows+N);//先按分数排序
    for(int i = 0; i < N; i++){
        node[i].index = i; //记录位置关系
        node[i].aid = cows[i].aid;
    }
    sort(node,node+N); //排序是为了寻找尽可能小的aid
    int l = 0, r = N-1;
    while(l < r){
        int mid = l+r+1>>1;
        //试探中位数。
        int f = check(mid);
        if(f == 1) l = mid;
        else if(f == 0) r = mid-1;
        else break;
    }
    printf("%d\\n",ans);
    return 0;
}
阅读更多
POJ-3579-Median(二分套二分)

POJ-3579-Median

题目描述：

Given N numbers, X1, X2, … , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!

Note in this problem, the median is defined as the (m/2)-th smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.

输入：

The input consists of several test cases.
In each test case, N will be given in the first line. Then N numbers are given, representing X1, X2, … , XN, ( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )

输出：

For each test case, output the median in a separate line.

输入示例：

1
2
3
4
4
1 3 2 4
3
1 10 2

输出示例：

1
2
1
8

题目大意：

给定N个数，求每两个数的差的绝对值一共C(N,2)个，排序后的中位数。

思路：

首先对于差的绝对值，我们只需要预先对数组进行排序，作后面对前面的差就不会出现负数。

我们考虑二分来解决该问题。答案是排序后的中位数，具有单调性，所以可以使用二分。我们先找到一个目标值，用这个目标值去判断是否为要求的中位数。

如何判断该数是否满足条件呢？
如果枚举全部这C(N,2)个数需要O(N2)的复杂度，超出了题目的要求，所以要寻找新的方案。我们已经将原数组排好序了，以每一项开始到数组最后，我们二分的寻找这里的所有的关系（i与i+1,i+2,…,N-1）中，满足：

1
arr[j] - arr[i] <= x

的一共有几项。

统计出项数与中位数作比较，就可以判断目标值是否满足条件。

Solution：

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
/*
 * @Date: 2019-10-05 13:59:05
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-10-05 14:48:00
 */
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAXN = 1e5+10;

int N;
int arr[MAXN];

bool check(int x){
    int cnt = 0;
    int M = N*(N-1)/2;
    M = (M+1)/2;
    for(int i = 0; i < N; i++){
        int l = i, r = N-1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(arr[mid] - arr[i] <= x) l = mid;
            else r = mid-1;
        }
        cnt += l-i;
        // arr[mid] - arr[i] <= x -----> arr[mid] <= arr[i]+x
        // 所以找arr[i]+x 的 upper_bound。
        // (upper_bound(arr,arr+N,arr[i]+x)-arr)-1 长度
        // (upper_bound(arr,arr+N,arr[i]+x)-arr)-i-1 //减去偏移量
        // cnt += (upper_bound(arr,arr+N,arr[i]+x)-arr)-i-1;
    }
    return cnt >= M;
}

int main(){
    freopen("in.txt","r",stdin); 
    while(scanf("%d",&N)!=EOF && N){
        for(int i = 0; i < N; i++){
            scanf("%d",&arr[i]);
        }
        sort(arr,arr+N);
        int l = 0, r = arr[N-1];
        //对结果进行二分
        while(l < r){
            int mid = l+r>>1;
            // 检查该结果是否大于等于总数的一半，
            if(check(mid)) r = mid;
            else l = mid+1;
        }
        printf("%d\\n",l);
    }
    return 0;
}
阅读更多
首页 归档 标签 关于 搜索