POJ-2976-Dropping tests

题目描述：

In a certain course, you take n tests. If you get ai out of bi questions correct on test i, your cumulative average is defined to be

Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.

Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is

However, if you drop the third test, your cumulative average becomes

输入：

The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ ai ≤ bi ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

输出：

For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.

输入示例：

1
2
3
4
5
6
7

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

输出示例：

1
2

83
100

提示：

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

题目大意：

有N个考试，每个考试有ai和bi两个值，最后成绩由上面的公式求得。幸运的是，可以放弃K个科目，求最大化最后的成绩。(输出乘100后四舍五入的结果)

思路：

由题意可知当，当n-k个科目组成最优解时，再增加别的科目，解一定不如原来的解，放弃掉k个科目是最好的方案。

于是，题目就变成了最小化平均值的问题，另外在注意下取整时的四舍五入就好了。

最小化平均值:

有n个物品的重量和价值分别为wi和vi，从中选择k个物品使得单位重量的价值最大。

对于这个问题，我们可以用二分搜索解决，先来看看判断条件：
设最大值为x，则需要满足 ∑vi / ∑wi >=x，把不等式进行变形，就得到了 ∑ ( vi - x wi )>=0，于是判断就成了，对 vi-xwi 的值进行排序之后贪心进行选择，判断前n-k个的和是否不小于0。判断的复杂度是O（nlogn）。

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

/*
 * @Date: 2019-09-28 16:40:15
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-09-29 18:14:27
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int MAXN = 1000+10;
int n,k;
struct node{
    int a,b;
}num[MAXN];

double f[MAXN];


bool check(double x){
    for(int i = 0; i < n; i++) f[i] = num[i].a - x*num[i].b;
    sort(f,f+n);
    double sum = 0;
    for(int i = 0; i <n-k; i++) sum += f[n-1-i];
    return sum >= 0;
}

int main(){
    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&k)!= EOF && n+k){
        for(int i = 0; i < n; i++){
            scanf("%d",&num[i].a);
        }
        for(int i = 0; i < n; i++){
            scanf("%d",&num[i].b);
        }
        double l = 0, r = 1e9;
        for(int i = 0; i < 100; i++){
            double mid = (l+r)/2;
            if(check(mid)) l = mid;
            else r = mid;
        }
 
		printf("%d\\n", int(l*100+0.5));

        // int ans = 100 * (l+0.005);
		// printf("%d\\n", ans);
    }

}

Cow Acrobats

题目描述：

Farmer John’s N (1 <= N <= 50,000) cows (numbered 1..N) are planning to run away and join the circus. Their hoofed feet prevent them from tightrope walking and swinging from the trapeze (and their last attempt at firing a cow out of a cannon met with a dismal failure). Thus, they have decided to practice performing acrobatic stunts.

The cows aren’t terribly creative and have only come up with one acrobatic stunt: standing on top of each other to form a vertical stack of some height. The cows are trying to figure out the order in which they should arrange themselves ithin this stack.

Each of the N cows has an associated weight (1 <= W_i <= 10,000) and strength (1 <= S_i <= 1,000,000,000). The risk of a cow collapsing is equal to the combined weight of all cows on top of her (not including her own weight, of course) minus her strength (so that a stronger cow has a lower risk). Your task is to determine an ordering of the cows that minimizes the greatest risk of collapse for any of the cows.

输入：

• Line 1: A single line with the integer N.

• Lines 2..N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i.

输出：

• Line 1: A single integer, giving the largest risk of all the cows in any optimal ordering that minimizes the risk.

输入示例：

1
2
3
4

3
10 3
2 5
3 3

输出示例：

1

2

提示：

OUTPUT DETAILS:

Put the cow with weight 10 on the bottom. She will carry the other two cows, so the risk of her collapsing is 2+3-3=2. The other cows have lower risk of collapsing.

题目大意：

有N头牛，每个牛有一定的重量w和力量s，将这N头牛叠罗汉，每头牛有一个风险值，为它背上所有牛的重量减去他的力量。求最大风险值，并要求最大风险值尽可能小。

思路：

该题就是要找到一个最优排列，让最大风险值尽可能小，显然的，重的牛应该尽可能的安排在下方，同样，力气大的牛也应该尽可能安排在下方。

结论:

将力量与重量之和从小到大排列。

证明一：

对于每头牛而言，将它与它上面的牛作为一个整体，总的重量为sum_w，则该牛的风险值为:

1

(sum_w-w-s)=(sum_w-(w+s))

我们要想取到最优解，就要sum_w-(w+s)的值最小，w+s就应该最大，所以w+s越大越应该在下面。

证明二：

假设当前的排列是最优的。任意位置上有第一头牛和第二头牛，第一头牛在第二头牛的上面，第一头牛上面的重量总和为sum，第一头牛和第二头牛的重量和力量分别为w1、s1、w2、s2，可以知道两头牛的危险值分别为 a = sum-s1, b = sum+w1-s2。
现在调换两头牛的位置，则a1 = sum+w1-s1, b1 = sum-s2。
因为之前是最优解，可得：

1
2

sum+w2-s1 >= sum+w1-s2
w2-s1 >= w1-s2

移项可得：

1

w2+s2 >= w1+s1

所以重量与力量和越大越在下方。

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

/*
 * @Date: 2019-09-27 23:11:05
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-09-28 11:43:09
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int MAXN = 5e4+10;
int N;

struct node{
    int w,s;
}a[MAXN];

bool cmp(node a, node b){
    return a.s+a.w > b.s+b.w;
}

int main(){
    scanf("%d",&N);
    long long sum = 0;
    for(int i = 0; i < N; i++){
        scanf("%d%d",&a[i].w,&a[i].s);
        sum += a[i].w;
    }
    sort(a,a+N,cmp);
    long long ans = -0x3f3f3f;
    for(int i = 0; i < N; i++){
        sum -= a[i].w;
        ans = max(ans,sum-a[i].s);
    }
    
    printf("%lld\\n",ans);
    return 0;
}

POJ-3276-Face The Right Way

题目描述：

Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K ≤ N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same location as before, but ends up facing the opposite direction. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

输入：

Line 1: A single integer: N
Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.

输出：

Line 1: Two space-separated integers: K and M

输入示例：

1
2
3
4
5
6
7
8

7
B
B
F
B
F
B
B

输出示例：

1

3 3

暗示：

For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)

题目大意：

有N头牛，牛要么朝前要么朝后，一次操作只可以翻转区间内的所有牛，问最小的翻转次数和相应最小的翻转区间。

思路：

首先，这是一个开关问题，一般性的开关问题具有两个性质：

• 切换状态的顺序对结果不影响。

• 一个开关按偶数次等于不按。

解决这个问题光有这两性质还不够，我们先求如果知道了区间长度K，如何求最小翻转次数M。

我们先选择考虑最左端的牛，如果该牛朝向前，则不需要翻转，所以范围可以缩减1，如果该牛朝向后，则必须翻转该区间了。我们贪心的翻转遇到的第一个朝向后的牛，就可以求出来最少的翻转次数了。

这样我们枚举K,并且每个K都需要检查N-K+1个区间，每个区间的检查又需要O(N)的时间，所以总的时间为O(N^3)。达不到题目要求的时限。

优化：

我们的目标是将所有的朝向后面的牛翻转，所以牛朝向决定了该区间是否发生翻转。我们将关注点移动到每个具体的牛与之前已经翻转的次数的关系上。

对于每个牛，与所在区间的已翻转次数有下列四种情况：

• 当前牛朝向前，已经翻转了偶数次。

• 当前牛朝向后，已经翻转了奇数次。

• 当前牛朝向前，已经翻转了奇数次。

• 房钱牛朝向后，已经翻转了偶数次。

我们结合前面开关问题的第二条性质发现：前两种情况不需要进行任何操作。后两种情况则需要进行一次翻转。所以结论就是：

如果朝向前为0，朝向后为1，则

当前牛的朝向 + 之前已经翻转的次数 = 奇数

的时候则说明该翻转了。

这样，可以在常数时间内知道每个区间的翻转次数。优化到了O(N^2)，能在时限内解决了。

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
58
59
60
61
62

/*
 * @Date: 2019-09-17 17:05:23
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-09-17 18:13:33
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
int N,K,M;
const int MAXN = 1e5+10;
int dir[MAXN];
int f[MAXN];

int cal(int k){
    // 表示区间[i, i+k-1] 是否翻转
    memset(f,0,sizeof(f));
    int sum = 0;//区间内翻转的次数
    int res = 0;
    for(int i = 0; i + k-1 < N; i++){
        //当牛的朝向与之前已翻转的次数。
        if((dir[i] + sum) % 2 != 0){
            res++;
            f[i] = 1;
        }
        //更新翻转次数
        sum += f[i];
        //固定区间
        if(i - k + 1 >= 0){
            sum -= f[i-k+1];
        }
    }
    //由于前n-k+1个 已经翻转到正面了，只有当后面的牛都不用翻转才合法。
    for(int i = N-k+1; i < N; i++){
        if((dir[i] + sum) % 2 != 0) return -1;
        //固定区间
        if(i - k + 1 >= 0) sum -= f[i-k+1];
    }
    return res;
}

int main(){
    freopen("in.txt","r",stdin);
    scanf("%d",&N);
    K = 1, M = N;
    char c[3];
    for(int i = 0; i < N; i++){
        scanf("%s",c);
        if(c[0] == 'B') dir[i] = 1;
    }   
    //枚举K
    for(int k = 1; k <= N; k++){
        int m = cal(k);
        if(m >= 0 && m < M){
            M = m;
            K = k;
        }
    }
    printf("%d %d",K,M);
}

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例:

1
2
3

输入: [0,1,0,2,1,0,1,3,2,1,2,1]

输出: 6

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

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        //小于等于两个是蓄不住水的。
        if(n <= 2) return 0;
        int ans = 0;
        int Max = -1;
        int k = -1;
        //找到至高点。
        for(int i = 0; i < n; i++){
            //先减去柱子本身高度
            ans -= height[i];
            if(Max < height[i]) Max = height[i], k = i;
        }
        //加上整个图的面积
        ans += n*Max;
        
        //从前到最高点，每次减去从开始到每个更高柱子高度的面积。
        int cur = height[0];
        int i = 1;
        while(i <= k){
            //i为从开始到当前柱子距离。height[i]-cur为高度差。
            if(height[i] > cur) ans -= i * (height[i]-cur),cur = height[i];
            i++;
        }
        cur = height[n-1];
        i = height.size()-2;
        while(i>=k){
            //i最后到当前柱子的距离。height[i]-cur为高度差。
            if(height[i] > cur) ans -= (n-i-1) * (height[i]-cur),cur = height[i];
            i--;
        }
        return ans;
    }
};

Solution2（单调栈）：

使用单调栈的原因是我们发现如果把每个柱子当作最低点，则接雨水的区域是左右第一个比当前柱子高的柱子所形成的区域乘以两者之间较小的柱子与当前柱子的高度差。所以我们进行单调栈寻找左右最近的比当前元素高的位置，来计算结果。

从直观来看，这样很像一层层的往里接水。（当然计算的时候不一定只是一层）

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

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<int> s;
        int ans = 0;
        for(int i = 0; i < n; i++){
            //找每个元素右边最近的大于他的值。//单调递减栈
            while(s.size() && height[i] > height[s.top()]){
                int top = s.top();
                s.pop();
                if(s.empty())break;
                //由于维持的是单调递减栈，所以当前栈顶是目前已知的最小一个元素，将栈顶取出，而新的栈顶元素与新发现的比它大的元素，一定能就组成边界，使得以目前最小元素为底，至左右边界中小的那一个，可以接到雨水。形象点就是一层一层的接。
                int dis = i-s.top()-1;
                ans += dis * (min(height[i],height[s.top()])-height[top]);
            }
            s.push(i);
        }
        return ans;
    }
};

Solution3（双指针）：

我们写第一种解法时发现，并没有必要去进行那么多减法，每次直接观察当前柱子高度与之前记录的最高柱子的高度关系，如果没有之前最高柱子高就说明可以接住雨水（因为我们每次寻找的是更高的柱子，直到全图最高柱子出现为止），这样可以直接计算该柱子之上可以接住的雨水。由于左右都是到了最高柱子就会停止，所以使用双指针来优化，每次选较小的柱子来计算，直到制高点。

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

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n-1;
        int lm = -1,rm = -1;
        int ans = 0;
        while(l < r){
            //从小的一方开始
            if(height[l] < height[r]){
                if(height[l] > lm){
                    lm = height[l];
                }else{
                    ans += lm-height[l];
                }
                l++;
            }else{
                if(height[r] > rm){
                    rm = height[r];
                }else{
                    ans += rm-height[r];
                }
                r--;
            }
        }
        return ans;
    }
};

单调栈

一、概述：

单调栈是一种特殊的栈结构，他要维持栈内元素保持一种单调性，从而能很快速的在线判断当前元素与后进来的元素大小关系。

二、单调性质

为了维持单调性，在进栈时需要做元素的检查工作。以单调递增栈来说，如果发现要进栈的元素比目前栈顶元素小，如果此时将该元素进栈，必然会破坏单调性，所以需要对栈内元素进行调整工作：即如果该元素比栈顶元素小，则一定要将栈顶元素弹出，直到该元素不再比栈顶元素大或者栈为空时，可将该元素进栈。

三、功能用途

在进行调整工作时，由于栈内元素时刻保持单调性，所以在遇见要进栈的元素比栈顶元素小时，对于当前栈顶元素，这个要进栈的元素是它第一次见到的比它小的元素。利用这一性质，我们就发现了单调栈的一个主要用途：求一个元素左/右边第一个比它大/小的元素。

四、具体做法

对于具体怎么求比它大的元素还是比它小的元素，可以通过分析发现，求值的时机是在要进栈的元素破坏了当前栈所保持的单调性，即与当前栈保持的单调性相反。所以我们可以说：

• 如果求比当前元素大的元素的位置，可以建立单调递减栈。

• 如果求比当前元素小的元素的位置，可以建立单调递增栈。

那如何求左边的或者右边的目标元素位置呢？

我们稍加分析就会知道：无论求哪个方向的元素，目标元素都一定要在当前元素之后进栈。所以可以得到：

• 求当前元素左边的比该元素大/小的元素，要从右向左依次添加。

• 求当前元素右边的比该元素大/小的元素，要从左向右依次添加。

由于我们需要求得每个元素的目标元素位置，但在一轮循环完毕后，栈中还存在符合单调性但没出栈的元素。也就是说当前栈内的每个元素都是没有与之相匹配的目标元素位置的。这时就要根据情况单独进行处理。

通常的处理方式是在循环操作结束时，再往栈内添加一个违反单调性的并且比所有的元素都要大的最值，迫使栈中的所有元素弹出。

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12

//例：单调递减栈。 找当前数的左边的第一个比当前数大的值的位置。
arr[0] = 2000000100;//最后位置添加一个最值。
for(int i = N; i >= 0; i--){
    //找到了比当前栈顶大的数，更新值
    while(stk.size() && arr[i] > arr[stk.top()]){
        对该stk.top()进行需求操作。
        stk.pop();
    }
    stk.push(i);
}
//将最后一个元素弹出。
stk.pop();

POJ-2796-FeelGood

题目描述：

Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good or bad days influent people’s memories about some period of life.

A new idea Bill has recently developed assigns a non-negative integer value to each day of human life.

Bill calls this value the emotional value of the day. The greater the emotional value is, the better the daywas. Bill suggests that the value of some period of human life is proportional to the sum of the emotional values of the days in the given period, multiplied by the smallest emotional value of the day in it. This schema reflects that good on average period can be greatly spoiled by one very bad day.

Now Bill is planning to investigate his own life and find the period of his life that had the greatest value. Help him to do so.

输入：

The first line of the input contains n - the number of days of Bill’s life he is planning to investigate(1 <= n <= 100 000). The rest of the file contains n integer numbers a1, a2, … an ranging from 0 to 106 - the emotional values of the days. Numbers are separated by spaces and/or line breaks.

输出：

Print the greatest value of some period of Bill’s life in the first line. And on the second line print two numbers l and r such that the period from l-th to r-th day of Bill’s life(inclusive) has the greatest possible value. If there are multiple periods with the greatest possible value,then print any one of them.

输入示例：

1
2

6
3 1 6 4 5 2

输出示例：

1
2

60
3 5

题目大意：

给定一串数字，求一区间，使得区间内的每个数之和乘以区间内最小值最大，并求出区间范围。

思路：

初次看，只能暴力枚举每一个区间，复杂度为O(n2)。

然后我们思考对于每个数，如果把它当做最小数，我们看他能向左右延伸到的最长区间范围，然后在这些区间内选一个符合条件最大的即可。

这就将问题转化为求每一个数左/右边尽可能远的大于等于该数的数的位置，进一步转化为求每个数的左右边遇到的第一个小于该数的位置，再往延伸的反方向退一格。这明显是单调栈问题。所以可以将复杂度降到O(n)。

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
58
59

/*
 * @Date: 2019-09-04 17:29:23
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-09-06 22:01:01
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int MAXN = 100010;
int a[MAXN],R[MAXN],L[MAXN],ll,rr;
long long sum[MAXN],ans = -1;
int N;
stack<int> s;
int main(){

    //思路：将枚举区间转化为以每个点为最低点，求向左和向右最多可以延长的长度。再转化一下就是求每个数左边或者右边第一个比它小的元素后 再往回退一格（L+1,R-1)。然后求区间内的最大值。
    //freopen("in.txt","r",stdin);
    scanf("%d",&N);
    a[0] = -1;
    a[N+1] = -1;
    for(int i = 1; i <= N; i++) scanf("%d",&a[i]),sum[i] = sum[i-1] + a[i];
    //求每个元素的左边第一个比它小的元素，加一 ----> 找大于等于该数的最前一个数的位置。

    //从右到左  单调递增栈
    for(int i = N; i >= 0; i--){
        while(s.size() && a[i] < a[s.top()]) {
            L[s.top()] = i+1;
            s.pop();
        }
        s.push(i);
    }
    s.pop();

    
    //求每个元素的右边第一个比它小的元素 减一 ----> 大于等于该数的最后一个数的位置
    //从左到右，单调递增栈
    for(int i = 1; i <= N+1; i++){
        while(s.size() && a[i] < a[s.top()]){
            R[s.top()] = i-1;
            s.pop();
        }
        s.push(i);
    }


    for(int i = 1; i <= N; i++){
        if((sum[R[i]] - sum[L[i]-1])*a[i] > ans){
            ans = (sum[R[i]] - sum[L[i]-1])*a[i];
            ll = L[i];
            rr = R[i];
        }
    }
    printf("%lld\\n%d %d\\n",ans,ll,rr);

    return 0;
}

这里由于是单调递增栈，所以在循环最后给他压进一个最小值，让栈内元素都弹出，做到代码简化。

POJ-3250-Bad Hair Day

题目描述：

Some of Farmer John’s N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows’ heads.

Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

Consider this example:

1
2
3
4
5
6
7

=
=       =
=   -   =         Cows facing right -->
=   =   =
= - = = =
= = = = = =
1 2 3 4 5 6

• Cow#1 can see the hairstyle of cows #2, 3, 4
• Cow#2 can see no cow’s hairstyle
• Cow#3 can see the hairstyle of cow #4
• Cow#4 can see no cow’s hairstyle
• Cow#5 can see the hairstyle of cow 6
• Cow#6 can see no cows at all!

Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

输入：

Line 1: The number of cows, N.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.

输出：

Line 1: A single integer that is the sum of c1 through cN.

输入示例：

1
2
3
4
5
6
7

6
10
3
7
4
12
2

输出示例：

1

5

题目大意：

有一排奶牛，每个奶牛可以看到它右边身高严格比它小的奶牛发型，问这一排奶牛可以看到的奶牛发型总数。

思路：

这道题是单调栈模板题。

具体做法就是在当前奶牛的右边找一个大于等于（原题说要严格小于，所以等于也算边界）它身高的奶牛的位置（由于求大于等于，所以维持一个单调递减栈），然后两者位置之差再减一就是中间的奶牛数量，每一个奶牛都做此操作即可求得结果。当然有一种情况是它找不到右边身高大于等于它的奶牛。这时可以把最后一个奶牛有一个无限高的奶牛，然后用该位置去减栈中每个奶牛的位置（n+1-x-1 = n-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

/*
 * @Date: 2019-09-04 16:39:06
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-09-06 21:41:17
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>

using namespace std;
struct node{
    int a,x;
    node(){}
    node(int _a, int _x):x(_x),a(_a){}
};

stack<node> s;

int main(){
    //freopen("in.txt","r",stdin);
    int n;
    long long ans = 0;
    scanf("%d",&n);
    node temp;
    for(int i = 1; i <= n; i++){
        scanf("%d",&temp.a);
        temp.x = i;
        //单调递减栈
        //找到了第一个比当前栈顶大的值（刚读入的值）。
        while(s.size() && s.top().a <= temp.a){
            //计算坐标差
            ans += i-s.top().x-1;
            s.pop();
        }
        s.push(temp);
    }
    //当前栈顶元素的右边没有比他更高的元素了，用最右边的无限高减去该元素位置。
    while(s.size()){
        ans += n-s.top().x;
        s.pop();
    }
    printf("%lld\\n",ans);
    return 0;
}

P1901 发射站

题目描述：

某地有 N 个能量发射站排成一行，每个发射站 i 都有不相同的高度 Hi，并能向两边（当 然两端的只能向一边）同时发射能量值为 Vi 的能量，并且发出的能量只被两边最近的且比 它高的发射站接收。

显然，每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受，特别是为了安 全，每个发射站接收到的能量总和是我们很关心的问题。由于数据很多，现只需要你帮忙计 算出接收最多能量的发射站接收的能量是多少。

输入格式：

第 1 行：一个整数 N;

第 2 到 N+1 行：第 i+1 行有两个整数 Hi 和 Vi，表示第 i 个人发射站的高度和发射的能量值。

输出格式：

输出仅一行，表示接收最多能量的发射站接收到的能量值，答案不超过 longint。

输入样例：

1
2
3
4

3
4 2 
3 5 
6 10

输出样例：

1

7

说明/提示：

对于 40%的数据，1<=N<=5000；1<=Hi<=100000；1<=Vi<=10000;

对于 70%的数据，1<=N<=100000；1<=Hi<=2,000,000,000；1<=Vi<=10000;

对于 100%的数据，1<=N<=1000000;1<=Hi<=2,000,000,000；1<=Vi<=10000。

题目解析：

题目中有一句至关重要的话：发出的能量只被两边最近的且比 它高的发射站接收。

这句话揭露了解法：使用单调栈。

将题目精简下，留其核心就是要分别求每个数左边和右边碰到的第一个比它大的数的位置。

这是经典的单调栈可以解决的问题，所以直接写两个单调栈：一个求左边的位置，一个求右边的位置，找到位置后将其能量值存起来，在其中找一个最大值即可。

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

/*
 * @Date: 2019-09-05 21:32:02
 * @LastEditors: BeckoninGshy
 * @LastEditTime: 2019-09-05 23:10:34
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long LL;

const int MAXN = 1000010;

LL arr[MAXN],s[MAXN],sum[MAXN],N,ans = -1;
stack<LL> stk;
int main(){
    //freopen("in.txt","r",stdin);
    scanf("%lld",&N);
    arr[0] = 2000000100;
    arr[N+1] = 2000000100;
    for(int i = 1; i <= N; i++){
        scanf("%lld%lld",&arr[i],&s[i]);
    }
    //找一个数左右两边离该数最近的并且比该数大的数的位置
    
    //单调递减栈。 找当前数的右边目标数
    for(int i = 1; i <= N+1; i++){
        //找到了比当前栈顶大的数，更新值
        while(stk.size() && arr[i] > arr[stk.top()]){
            sum[i] += s[stk.top()];
            stk.pop();
        }
        stk.push(i);
    }
    stk.pop();
    

    //单调递减栈。 找当前数的左边目标数
    for(int i = N; i >= 0; i--){
        //找到了比当前栈顶大的数，更新值
        while(stk.size() && arr[i] > arr[stk.top()]){
            sum[i] += s[stk.top()];
            stk.pop();
        }
        stk.push(i);
    }
    stk.pop();
    for(int i = 1; i <= N; i++) ans = max(ans,sum[i]);
    printf("%lld",ans);
    return 0;
}

概念：

最小生成树是一副连通加权无向图中一棵权值最小的生成树。

在现实生活中，经常要求在类似网络的复杂关系中，既要面面俱到（任意两个结点之间都可以访问到），又要使所用成本尽可能的小。最小生成树就是解决相关问题的。

一个连通图可能有多个不同的最小生成树，但是其权值之和一定相等。一棵最小生成树一定有N个顶点，N-1条边。通过对生成树关注的角度不同，有相应两种不同但同样常用的算法。

一、Prim算法：

prim算法是按每一步为一棵生长中的树添加一条边，该数最开始只有一个顶点，然后会添加v-1条边。

每次总是选择一条与生长中的树和图中与该树相连的部分所形成的具有最小权值的横切边添加到该生成树中。

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

int G[MAXN][MAXN];//权值矩阵
int vis[MAXN];//记录访问
int lowc[MAXN];//记录与树连接的边的权重
memset(G,INF,sizeof(G));
memset(vis,false,sizeof(vis));
memset(lowc,INF,sizeof(lowc));


//标号0-n-1，返回最小生成树的权值，返回-1表示不连通
int Prim(int n){
	int ans = 0;
	
	//从0节点开始
	vis[0] = true;
	//首先更新与0结点直接相连的边的权值。
	for(int i = 1; i < n; i++) lowc[i] = G[0][i];
    //循环n-1次
	for(int i = 1; i < n; i++){
		int minc = INF;
		int p = -1;
		//找到与当前树相连并且权值最小的边。
		for(int j = 0; j < n; j++){
			if(!vis[j]&&minc > lowc[j]){
				minc = lowc[j];
				p = j;
			}
		}
		//不连通
		if(minc == INF) return -1;
		//更新树的权值
		ans += minc;
		vis[p] = true;
		//继续更新新树的最小权值数组。
		for(int j = 0; j < n; j++){
			if(!vis[j]&&lowc[j] > G[p][j])
				lowc[j] = G[p][j];
		}
	}
	return ans;
}

二、 Kruskal算法

算法流程：

• 新建图G，G中拥有原图中相同的节点，但没有边。

• 将原图中所有的边按权值从小到大排序

• 从权值最小的边开始，如果这条边连接的两个结点与图G中不在同一个连通分量重，则添加这条边到图G中。

• 重复3，直至图G中所有的结点都在同一个连通分量中。一共需要合并n-1次。

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

const int MAXN = 1010;//最大点数 
const int MAXM = 10000;//最大边数
 
int F[MAXN]; //并查集使用

//存储边的信息，起点，终点，权值
struct Edge{
	int u,v,w;
}edge[MAXM]; 
int tol = 0;//边数，加边前赋值为0

//加边函数
void addedge(int u,int v,int w){
	edge[tol].u = u;
	edge[tol].v = v;
	edge[tol++].w = w;
} 
//比较函数，排序用
bool cmp(Edge a,Edge b){
	return a.w < b.w;
} 
//查找元素所属集合。路径压缩版
int find(int x){
	return F[x] == -1 ? x : F[x] = find(F[x]);
}

//传入点数，返回最小生成树的权值，如果不连通返回-1
int Kruskal(int n){
	memset(F,-1,sizeof(F));
	//先对边排序
	sort(edge,edge+tol,cmp);
	int cnt = 0; //计算加入的边数。
	int ans = 0;
	//最多循环tol次
	for(int i = 0; i < tol; i++){
		int u = edge[i].u;
		int v = edge[i].v;
		int w = edge[i].w;
		int t1 = find(u);
		int t2 = find(v);
		//如果属于不同集合，合并
		if(t1 != t2){
			ans+= w;
			F[t1] = t2;
			cnt++;
		}
		//共需合并n-1次，已经完成，可提前结束
		if(cnt == n-1) break;
	} 
	if(cnt < n-1) return -1;//不连通
	return ans; 
}

对于稀疏图，选择Kruskal算法较优，而对于稠密图，Prim算法会更高效。

此外还有最大生成树，其实只要将图中的权值取反一下，就可以求得最大生成树，或者在kruskal算法，按从大到小排序之后再合并，得出来的也是最大生成树。

POJ-3660-Cow Contest

题目描述：

N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

输入：

• Line 1: Two space-separated integers: N and M

• Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B

输出：

Line 1: A single integer representing the number of cows whose ranks can be determined 　

输入示例：

1
2
3
4
5
6

5 5
4 3
4 2
3 2
1 2
2 5

输出示例：

1

2

题目大意：

有N头牛，现在给出M个输赢列表（第一代表赢，第二代表输），并且实力是绝对的（这句话很重要）。要求你确定谁的排名是确定的，输出确定的个数。

思路：

使用传递闭包来确定赢的关系，并通过判断其中一头牛与其他牛是否都有联系（赢了别的牛，或输给了别的牛）。如果与其余N-1条牛都有联系，说明该牛的排名是确定的。

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

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;
const int MAXN = 200;
const int INF = 0x3f3f3f3f;

int G[MAXN][MAXN];
int N,M;
int main(){
    freopen("in.txt","r",stdin);
    memset(G,0,sizeof(G));
    scanf("%d%d",&N,&M);
    for(int i = 0; i < M; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        //生成a赢b的关系图
        G[a][b] = 1;
    }
    
    for(int k = 1; k <= N; k++)
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                //B>C，A>B，说明A>C
                if(G[i][k] && G[k][j]) G[i][j] = 1;

    /*
    只有当一个点与其他个点都有联系（或赢或输）,才可以确定该点
    */
    int ans = 0;
    for(int i = 1; i <= N; i++){
        int sum = 0;
        for(int j = 1; j <= N; j++){
        // 又因为该题有唯一的赢输判定，所以与其他各点都有联系可以直接表示为加的和为N-1
        // 否则只能一一判定当前点与其他个点的关系。
            sum = sum + G[i][j] + G[j][i];
        }
        if(sum == N-1) ans++;
    }
    printf("%d\\n",ans);

    return 0;
}