OJ – 第5页 – 柳婼の blog

1060. Are They Equal (25)-PAT甲级真题（科学计数法）

If a machine can save only 3 significant digits, the float numbers 12300 and 12358.9 are considered equal since they are both saved as 0.123*105 with simple chopping. Now given the number of significant digits on a machine and two float numbers, you are supposed to tell if they are treated equal in that machine.

Input Specification:

Each input file contains one test case which gives three numbers N, A and B, where N (<100) is the number of significant digits, and A and B are the two float numbers to be compared. Each float number is non-negative, no greater than 10100, and that its total digit number is less than 100.

Output Specification:

For each test case, print in a line “YES” if the two numbers are treated equal, and then the number in the standard form “0.d1…dN*10^k” (d1>0 unless the number is 0); or “NO” if they are not treated equal, and then the two numbers in their standard form. All the terms must be separated by a space, with no extra space at the end of a line.

Note: Simple chopping is assumed without rounding.

Sample Input 1:
3 12300 12358.9
Sample Output 1:
YES 0.123*10^5
Sample Input 2:
3 120 128
Sample Output 2:
NO 0.120*10^3 0.128*10^3

题目大意：给出两个数，问将它们写成保留N位小数的科学计数法后是否相等。如果相等，输出YES，输出他们的科学记数法表示方法。如果不相等输出NO，分别输出他们的科学计数法
分析：
1. cnta 和 cntb 通过扫描字符串得到小数点所在的下标（初始化cnta cntb为字符串长度，即下标为strlen(str））
2. 考虑到可能前面有多余的零，用 p 和 q 通过扫描字符串使 p q 开始于第一个非0（且非小数点）处的下标
3. 如果cnta >= p ，说明小数点在第一个开始的非0数的下标的右边，那么科学计数法的指数为cnta – p ; 否则应该为cnta – p + 1; 字符串b同理。
4. 如果 p 和 q 等于字符串长度，说明字符串是 0，此时直接把 cnta（或者cntb）置为0，因为对于0来说乘以几次方都是相等的，如果不置为0可能会出现两个0比较导致判断为它们不相等
5. indexa = 0开始给新的A数组赋值，共赋值n位除去小数点外的正常数字，从p的下标开始。如果p大于等于strlen，说明字符串遍历完毕后依旧没能满足需要的位数，此时需要在A数组后面补上0直到满足n位数字。indexb同理，产生新的B数组
6. 判断A和B是否相等，且cnta和cntb是否相等。如果相等，说明他们用科学计数法表示后是相同的，输出YES，否则输出NO，同时输出正确的科学计数法
注意：
– 10的0次方和1次方都要写。
– 题目中说，无需四舍五入。
– 数组开大点，虽然只有100位，但是很有可能前面的0很多导致根本不止100位。一开始开的110，几乎没有AC的任何测试点。。后来开了10000就AC了~

#include <iostream>
#include <cstring>
using namespace std;
int main() {
    int n, p = 0, q = 0;
    char a[10000], b[10000], A[10000], B[10000];
    scanf("%d%s%s", &n, a, b);
    int cnta = strlen(a), cntb = strlen(b);
    for(int i = 0; i < strlen(a); i++) {
        if(a[i] == '.') {
            cnta = i;
            break;
        }
    }
    for(int i = 0; i < strlen(b); i++) {
        if(b[i] == '.') {
            cntb = i;
            break;
        }
    }
    int indexa = 0, indexb = 0;
    while(a[p] == '0' || a[p] == '.') p++;
    while(b[q] == '0' || b[q] == '.') q++;
    if(cnta >= p)
        cnta = cnta - p;
    else
        cnta = cnta - p + 1;
    if(cntb >= q)
        cntb = cntb - q;
    else
        cntb = cntb - q + 1;
    if(p == strlen(a))
        cnta = 0;
    if(q == strlen(b))
        cntb = 0;
    while(indexa < n) {
        if(a[p] != '.' && p < strlen(a))
            A[indexa++] = a[p];
        else if(p >= strlen(a))
            A[indexa++] = '0';
        p++;
    }
    while(indexb < n) {
        if(b[q] != '.' && q < strlen(b))
            B[indexb++] = b[q];
        else if(q >= strlen(b))
            B[indexb++] = '0';
        q++;
    }
    if(strcmp(A, B) == 0 && cnta == cntb)
        printf("YES 0.%s*10^%d", A, cnta);
    else
        printf("NO 0.%s*10^%d 0.%s*10^%d" , A, cnta, B, cntb);
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

int n, p = 0, q = 0;

char a[10000], b[10000], A[10000], B[10000];

scanf("%d%s%s", &n, a, b);

int cnta = strlen(a), cntb = strlen(b);

for(int i = 0; i < strlen(a); i++) {

if(a[i] == '.') {

cnta = i;

break;

}

for(int i = 0; i < strlen(b); i++) {

if(b[i] == '.') {

cntb = i;

break;

}

int indexa = 0, indexb = 0;

while(a[p] == '0' || a[p] == '.') p++;

while(b[q] == '0' || b[q] == '.') q++;

if(cnta >= p)

cnta = cnta - p;

else

cnta = cnta - p + 1;

if(cntb >= q)

cntb = cntb - q;

else

cntb = cntb - q + 1;

if(p == strlen(a))

cnta = 0;

if(q == strlen(b))

cntb = 0;

while(indexa < n) {

if(a[p] != '.' && p < strlen(a))

A[indexa++] = a[p];

else if(p >= strlen(a))

A[indexa++] = '0';

p++;

}

while(indexb < n) {

if(b[q] != '.' && q < strlen(b))

B[indexb++] = b[q];

else if(q >= strlen(b))

B[indexb++] = '0';

q++;

}

if(strcmp(A, B) == 0 && cnta == cntb)

printf("YES 0.%s*10^%d", A, cnta);

else

printf("NO 0.%s*10^%d 0.%s*10^%d" , A, cnta, B, cntb);

return 0;

}

1059. Prime Factors (25)-PAT甲级真题（素数表的建立）

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1^k1 * p2^k2 *…*pm^km.

Input Specification:

Each input file contains one test case which gives a positive integer N in the range of long int.

Output Specification:

Factor N in the format N = p1^k1 * p2^k2 *…*pm^km, where pi’s are prime factors of N in increasing order, and the exponent ki is the number of pi — hence when there is only one pi, ki is 1 and must NOT be printed out.

Sample Input:
97532468
Sample Output:
97532468=2^2*11*17*101*1291
题目大意：给出一个整数，按照从小到大的顺序输出其分解为质因数的乘法算式
分析：根号int的最大值不超过50000，先建立个50000以内的素数表，然后从2开始一直判断是否为它的素数，如果是就将a=a/i继续判断i是否为a的素数，判断完成后输出这个素数因子和个数，用state判断是否输入过因子，输入过就要再前面输出“*”

#include <cstdio>
#include <vector>
using namespace std;
vector<int> prime(50000, 1);
int main() {
    for(int i = 2; i * i < 50000; i++)
        for(int j = 2; j * i < 50000; j++)
            prime[j * i] = 0;
    long int a;
    scanf("%ld", &a);
    printf("%ld=", a);
    if(a == 1) printf("1");
    bool state = false;
    for(int i = 2; i < 50000 && a >= 2; i++) {
        int cnt = 0, flag = 0;
        while(prime[i] == 1 && a % i == 0) {
            cnt++;
            a = a / i;
            flag = 1;
        }
        if(flag) {
            if(state) printf("*");
            printf("%d", i);
            state = true;
        }
        if(cnt >= 2) printf("^%d", cnt);
    }
    if (a > 1) printf("%s%ld", state ? "*" : "", a);
    return 0;
}

#include <cstdio>

#include <vector>

using namespace std;

vector<int> prime(50000, 1);

int main() {

for(int i = 2; i * i < 50000; i++)

for(int j = 2; j * i < 50000; j++)

prime[j * i] = 0;

long int a;

scanf("%ld", &a);

printf("%ld=", a);

if(a == 1) printf("1");

bool state = false;

for(int i = 2; i < 50000 && a >= 2; i++) {

int cnt = 0, flag = 0;

while(prime[i] == 1 && a % i == 0) {

cnt++;

a = a / i;

flag = 1;

}

if(flag) {

if(state) printf("*");

printf("%d", i);

state = true;

}

if(cnt >= 2) printf("^%d", cnt);

}

if (a > 1) printf("%s%ld", state ? "*" : "", a);

return 0;

}

1053. Path of Equal Weight (30)-PAT甲级真题(树的遍历)

Given a non-empty tree with root R, and with weight Wi assigned to each tree node Ti. The weight of a path from R to L is defined to be the sum of the weights of all the nodes along the path from R to any leaf node L.

Now given any weighted tree, you are supposed to find all the paths with their weights equal to a given number. For example, let’s consider the tree showed in Figure 1: for each node, the upper number is the node ID which is a two-digit number, and the lower number is the weight of that node. Suppose that the given number is 24, then there exists 4 different paths which have the same given weight: {10 5 2 7}, {10 4 10}, {10 3 3 6 2} and {10 3 3 6 2}, which correspond to the red edges in Figure 1.

Snip20160820_53
Figure 1

Input Specification:
Each input file contains one test case. Each case starts with a line containing 0 < N <= 100, the number of nodes in a tree, M (< N), the number of non-leaf nodes, and 0 < S < 230, the given weight number. The next line contains N positive numbers where Wi (<1000) corresponds to the tree node Ti. Then M lines follow, each in the format:

ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 00.

Output Specification:

For each test case, print all the paths with weight S in non-increasing order. Each path occupies a line with printed weights from the root to the leaf in order. All the numbers must be separated by a space with no extra space at the end of the line.

Note: sequence {A1, A2, …, An} is said to be greater than sequence {B1, B2, …, Bm} if there exists 1 <= k < min{n, m} such that Ai = Bi for i=1, … k, and Ak+1 > Bk+1.

Sample Input:
20 9 24
10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2
00 4 01 02 03 04
02 1 05
04 2 06 07
03 3 11 12 13
06 1 09
07 2 08 10
16 1 15
13 3 14 16 17
17 2 18 19
Sample Output:
10 5 2 7
10 4 10
10 3 3 6 2
10 3 3 6 2
题目大意：给出树的结构和权值，找从根结点到叶子结点的路径上的权值相加之和等于给定目标数的路径，并且从大到小输出路径
分析：对于接收孩子结点的数据时，每次完全接收完就对孩子结点按照权值进行排序（序号变，根据权值变），这样保证深度优先遍历的时候直接输出就能输出从大到小的顺序。记录路径采取这样的方式：首先建立一个path数组，传入一个nodeNum记录对当前路径来说这是第几个结点（这样直接在path[nodeNum]里面存储当前结点的孩子结点的序号，这样可以保证在先判断return的时候，path是从0~numNum-1的值确实是要求的路径结点）。然后每次要遍历下一个孩子结点的之前，令path[nodeNum] = 孩子结点的序号，这样就保证了在return的时候当前path里面从0~nodeNum-1的值就是要输出的路径的结点序号，输出这个序号的权值即可，直接在return语句里面输出。
注意：当sum==target的时候，记得判断是否孩子结点是空，要不然如果不空说明没有到底部，就直接return而不是输出路径。。。（这对接下来的孩子结点都是正数才有用，负权无用）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int target;
struct NODE {
    int w;
    vector<int> child;
};
vector<NODE> v;
vector<int> path;
void dfs(int index, int nodeNum, int sum) {
    if(sum > target) return ;
    if(sum == target) {
        if(v[index].child.size() != 0) return;
        for(int i = 0; i < nodeNum; i++)
            printf("%d%c", v[path[i]].w, i != nodeNum - 1 ? ' ' : '\n');
        return ;
    }
    for(int i = 0; i < v[index].child.size(); i++) {
        int node = v[index].child[i];
        path[nodeNum] = node;
        dfs(node, nodeNum + 1, sum + v[node].w);
    }
    
}
int cmp1(int a, int b) {
    return v[a].w > v[b].w;
}
int main() {
    int n, m, node, k;
    scanf("%d %d %d", &n, &m, &target);
    v.resize(n), path.resize(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &v[i].w);
    for(int i = 0; i < m; i++) {
        scanf("%d %d", &node, &k);
        v[node].child.resize(k);
        for(int j = 0; j < k; j++)
            scanf("%d", &v[node].child[j]);
        sort(v[node].child.begin(), v[node].child.end(), cmp1);
    }
    dfs(0, 1, v[0].w);
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int target;

struct NODE {

int w;

vector<int> child;

};

vector<NODE> v;

vector<int> path;

void dfs(int index, int nodeNum, int sum) {

if(sum > target) return ;

if(sum == target) {

if(v[index].child.size() != 0) return;

for(int i = 0; i < nodeNum; i++)

printf("%d%c", v[path[i]].w, i != nodeNum - 1 ? ' ' : '\n');

return ;

}

for(int i = 0; i < v[index].child.size(); i++) {

int node = v[index].child[i];

path[nodeNum] = node;

dfs(node, nodeNum + 1, sum + v[node].w);

}

int cmp1(int a, int b) {

return v[a].w > v[b].w;

}

int main() {

int n, m, node, k;

scanf("%d %d %d", &n, &m, &target);

v.resize(n), path.resize(n);

for(int i = 0; i < n; i++)

scanf("%d", &v[i].w);

for(int i = 0; i < m; i++) {

scanf("%d %d", &node, &k);

v[node].child.resize(k);

for(int j = 0; j < k; j++)

scanf("%d", &v[node].child[j]);

sort(v[node].child.begin(), v[node].child.end(), cmp1);

}

dfs(0, 1, v[0].w);

return 0;

}

1045. Favorite Color Stripe (30)-PAT甲级真题（动态规划）

Eva is trying to make her own color stripe out of a given one. She would like to keep only her favorite colors in her favorite order by cutting off those unwanted pieces and sewing the remaining parts together to form her favorite color stripe.

It is said that a normal human eye can distinguish about less than 200 different colors, so Eva’s favorite colors are limited. However the original stripe could be very long, and Eva would like to have the remaining favorite stripe with the maximum length. So she needs your help to find her the best result.

Note that the solution might not be unique, but you only have to tell her the maximum length. For example, given a stripe of colors {2 2 4 1 5 5 6 3 1 1 5 6}. If Eva’s favorite colors are given in her favorite order as {2 3 1 5 6}, then she has 4 possible best solutions {2 2 1 1 1 5 6}, {2 2 1 5 5 5 6}, {2 2 1 5 5 6 6}, and {2 2 3 1 1 5 6}.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=200) which is the total number of colors involved (and hence the colors are numbered from 1 to N). Then the next line starts with a positive integer M (<=200) followed by M Eva’s favorite color numbers given in her favorite order. Finally the third line starts with a positive integer L (<=10000) which is the length of the given stripe, followed by L colors on the stripe. All the numbers in a line are separated by a space.

Output Specification:

For each test case, simply print in a line the maximum length of Eva’s favorite stripe.

Sample Input:
6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6
Sample Output:
7

题目大意：给出m中颜色作为喜欢的颜色（同时也给出顺序），然后给出一串长度为L的颜色序列，现在要去掉这个序列中的不喜欢的颜色，然后求剩下序列的一个子序列，使得这个子序列表示的颜色顺序符合自己喜欢的颜色的顺序，不一定要所有喜欢的颜色都出现。
分析：因为喜欢的颜色是不重复的，把喜欢的颜色的序列依次存储到数组中，book[i] = j表示i颜色的下标为j。先在输入的时候剔除不在喜欢的序列中的元素，然后把剩余的保存在数组a中。按照最长不下降子序列的方式做，对于从前到后的每一个i，如果它前面的所有的j，一下子找到了一个j的下标book[j]比book[i]小，此时就更新dp[i]使它 = max(dp[i], dp[j] + 1)；并且同时再每一次遍历完成一次j后更新maxn的值为长度的最大值，最后输出maxn～

#include <iostream>
#include <vector>
using namespace std;
int book[201], a[10001], dp[10001];
int main() {
    int n, m, x, l, num = 0, maxn = 0;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d", &x);
        book[x] = i;
    }
    scanf("%d", &l);
    for(int i = 0; i < l; i++) {
        scanf("%d", &x);
        if(book[x] >= 1)
            a[num++] = book[x];
    }
    for(int i = 0; i < num; i++) {
        dp[i] = 1;
        for(int j = 0; j < i; j++)
            if(a[i] >= a[j])
                dp[i] = max(dp[i], dp[j] + 1);
        maxn = max(dp[i], maxn);
    }
    printf("%d", maxn);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int book[201], a[10001], dp[10001];

int main() {

int n, m, x, l, num = 0, maxn = 0;

scanf("%d %d", &n, &m);

for(int i = 1; i <= m; i++) {

scanf("%d", &x);

book[x] = i;

}

scanf("%d", &l);

for(int i = 0; i < l; i++) {

scanf("%d", &x);

if(book[x] >= 1)

a[num++] = book[x];

}

for(int i = 0; i < num; i++) {

dp[i] = 1;

for(int j = 0; j < i; j++)

if(a[i] >= a[j])

dp[i] = max(dp[i], dp[j] + 1);

maxn = max(dp[i], maxn);

}

printf("%d", maxn);

return 0;

}

1098. Insertion or Heap Sort (25)-PAT甲级真题（堆排序）

According to Wikipedia:
Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either “Insertion Sort” or “Heap Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
Sample Output 1:
Insertion Sort
1 2 3 5 7 8 9 4 6 0
Sample Input 2:
10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9
Sample Output 2:
Heap Sort
5 4 3 1 0 2 6 7 8 9

题目大意：给出n和n个数的序列a和b，a为原始序列，b为排序其中的一个步骤，问b是a经过了堆排序还是插入排序的，并且输出它的下一步～

分析：插入排序的特点是：b数组前面的顺序是从小到大的，后面的顺序不一定，但是一定和原序列的后面的顺序相同～所以只要遍历一下前面几位，遇到不是从小到大的时候，开始看b和a是不是对应位置的值相等，相等就说明是插入排序，否则就是堆排序啦～

插入排序的下一步就是把第一个不符合从小到大的顺序的那个元素插入到前面已排序的里面的合适的位置，那么只要对前几个已排序的+后面一位这个序列sort排序即可～while(p <= n && b[p – 1] <= b[p]) p++；int index = p；找到第一个不满足条件的下标p并且赋值给index，b数组下标从1开始，所以插入排序的下一步就是sort(b.begin() + 1, b.begin() + index + 1)后的b数组～

堆排序的特点是后面是从小到大的，前面的顺序不一定，又因为是从小到大排列，堆排序之前堆为大顶堆，前面未排序的序列的最大值为b[1]，那么就可以从n开始往前找，找第一个小于等于b[1]的数字b[p]（while(p > 2 && b[p] >= b[1]) p–；），把它和第一个数字交换（swap(b[1], b[p])；），然后把数组b在1~p-1区间进行一次向下调整（downAdjust(b, 1, p – 1)；）～向下调整，low和high是需要调整的区间，因为是大顶堆，就是不断比较当前结点和自己的孩子结点哪个大，如果孩子大就把孩子结点和自己交换，然后再不断调整直到到达区间的最大值不能再继续了为止～

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void downAdjust(vector<int> &b, int low, int high) {
    int i = 1, j = i * 2;
    while(j <= high) {
        if(j + 1 <= high && b[j] < b[j + 1]) j = j + 1;
        if (b[i] >= b[j]) break;
        swap(b[i], b[j]);
        i = j; j = i * 2;
    }
}
int main() {
    int n, p = 2;
    scanf("%d", &n);
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    while(p <= n && b[p - 1] <= b[p]) p++;
    int index = p;
    while(p <= n && a[p] == b[p]) p++;
    if(p == n + 1) {
        printf("Insertion Sort\n");
        sort(b.begin() + 1, b.begin() + index + 1);
    } else {
        printf("Heap Sort\n");
        p = n;
        while(p > 2 && b[p] >= b[1]) p--;
        swap(b[1], b[p]);
        downAdjust(b, 1, p - 1);
    }
    printf("%d", b[1]);
    for(int i = 2; i <= n; i++)
        printf(" %d", b[i]);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

void downAdjust(vector<int> &b, int low, int high) {

int i = 1, j = i * 2;

while(j <= high) {

if(j + 1 <= high && b[j] < b[j + 1]) j = j + 1;

if (b[i] >= b[j]) break;

swap(b[i], b[j]);

i = j; j = i * 2;

}

int main() {

int n, p = 2;

scanf("%d", &n);

vector<int> a(n + 1), b(n + 1);

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

for(int i = 1; i <= n; i++) scanf("%d", &b[i]);

while(p <= n && b[p - 1] <= b[p]) p++;

int index = p;

while(p <= n && a[p] == b[p]) p++;

if(p == n + 1) {

printf("Insertion Sort\n");

sort(b.begin() + 1, b.begin() + index + 1);

} else {

printf("Heap Sort\n");

p = n;

while(p > 2 && b[p] >= b[1]) p--;

swap(b[1], b[p]);

downAdjust(b, 1, p - 1);

}

printf("%d", b[1]);

for(int i = 2; i <= n; i++)

printf(" %d", b[i]);

return 0;

}

1057. Stack (30)-PAT甲级真题（树状数组）

Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian — return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<= 105). Then N lines follow, each contains a command in one of the following 3 formats:

Push key
Pop
PeekMedian
where key is a positive integer no more than 105.

Output Specification:

For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print “Invalid” instead.

Sample Input:
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
Sample Output:
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

题目大意：现请你实现一种特殊的堆栈，它多了一种操作叫“查中值”，即返回堆栈中所有元素的中值。对于N个元素，若N是偶数，则中值定义为第N/2个最小元；若N是奇数，则中值定义为第(N+1)/2个最小元。
分析：用排序查询的方法会超时～～用树状数组，即求第k = (s.size() + 1) / 2大的数。查询小于等于x的数的个数是否等于k的时候用二分法更快～

#include <iostream>
#include <stack>
#define lowbit(i) ((i) & (-i))
const int maxn = 100010;
using namespace std;
int c[maxn];
stack<int> s;
void update(int x, int v) {
    for(int i = x; i < maxn; i += lowbit(i))
        c[i] += v;
}
int getsum(int x) {
    int sum = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}
void PeekMedian() {
    int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;
    while(left < right) {
        mid = (left + right) / 2;
        if(getsum(mid) >= k)
            right = mid;
        else
            left = mid + 1;
    }
    printf("%d\n", left);
}
int main() {
    int n, temp;
    scanf("%d", &n);
    char str[15];
    for(int i = 0; i < n; i++) {
        scanf("%s", str);
        if(str[1] == 'u') {
            scanf("%d", &temp);
            s.push(temp);
            update(temp, 1);
        } else if(str[1] == 'o') {
            if(!s.empty()) {
                update(s.top(), -1);
                printf("%d\n", s.top());
                s.pop();
            } else {
                printf("Invalid\n");
            }
        } else {
            if(!s.empty())
                PeekMedian();
            else
                printf("Invalid\n");
        }
    }
    return 0;
}

#include <iostream>

#include <stack>

#define lowbit(i) ((i) & (-i))

const int maxn = 100010;

using namespace std;

int c[maxn];

stack<int> s;

void update(int x, int v) {

for(int i = x; i < maxn; i += lowbit(i))

c[i] += v;

}

int getsum(int x) {

int sum = 0;

for(int i = x; i >= 1; i -= lowbit(i))

sum += c[i];

return sum;

}

void PeekMedian() {

int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;

while(left < right) {

mid = (left + right) / 2;

if(getsum(mid) >= k)

right = mid;

else

left = mid + 1;

}

printf("%d\n", left);

}

int main() {

int n, temp;

scanf("%d", &n);

char str[15];

for(int i = 0; i < n; i++) {

scanf("%s", str);

if(str[1] == 'u') {

scanf("%d", &temp);

s.push(temp);

update(temp, 1);

} else if(str[1] == 'o') {

if(!s.empty()) {

update(s.top(), -1);

printf("%d\n", s.top());

s.pop();

} else {

printf("Invalid\n");

}

} else {

if(!s.empty())

PeekMedian();

else

printf("Invalid\n");

}

return 0;

}