liuchuo – 第201页 – 我不管，反正我最萌～

1037. Magic Coupon (25)-PAT甲级真题（贪心算法）

The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use this coupon with a product, you may get N times the value of that product back! What is more, the shop also offers some bonus product for free. However, if you apply a coupon with a positive N to this bonus product, you will have to pay the shop N times the value of the bonus product… but hey, magically, they have some coupons with negative N’s!

For example, given a set of coupons {1 2 4 -1}, and a set of product values {7 6 -2 -3} (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.

Each coupon and each product may be selected at most once. Your task is to get as much money back as possible.

Input Specification:

Each input file contains one test case. For each case, the first line contains the number of coupons NC, followed by a line with NC coupon integers. Then the next line contains the number of products NP, followed by a line with NP product values. Here 1<= NC, NP <= 105, and it is guaranteed that all the numbers will not exceed 230.

Output Specification:

For each test case, simply print in a line the maximum amount of money you can get back.

Sample Input:
4
1 2 4 -1
4
7 6 -2 -3
Sample Output:
43
题目大意：给出两个数字序列，从这两个序列中分别选取相同数量的元素进行一对一相乘，问能得到的乘积之和最大为多少～
分析：把这两个序列都从小到大排序，将前面都是负数的数相乘求和，然后将后面都是正数的数相乘求和～

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int m, n, ans = 0, p = 0, q = 0;
    scanf("%d", &m);
    vector<int> v1(m);
    for(int i = 0; i < m; i++)
        scanf("%d", &v1[i]);
    scanf("%d", &n);
    vector<int> v2(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &v2[i]);
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    while(p < m && q < n && v1[p] < 0 && v2[q] < 0) {
        ans += v1[p] * v2[q];
        p++; q++;
    }
    p = m - 1, q = n - 1;
    while(p >= 0 && q >= 0 && v1[p] > 0 && v2[q] > 0) {
        ans += v1[p] * v2[q];
        p--; q--;
    }
    printf("%d", ans);
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

int m, n, ans = 0, p = 0, q = 0;

scanf("%d", &m);

vector<int> v1(m);

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

scanf("%d", &v1[i]);

scanf("%d", &n);

vector<int> v2(n);

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

scanf("%d", &v2[i]);

sort(v1.begin(), v1.end());

sort(v2.begin(), v2.end());

while(p < m && q < n && v1[p] < 0 && v2[q] < 0) {

ans += v1[p] * v2[q];

p++; q++;

}

p = m - 1, q = n - 1;

while(p >= 0 && q >= 0 && v1[p] > 0 && v2[q] > 0) {

ans += v1[p] * v2[q];

p--; q--;

}

printf("%d", ans);

return 0;

}

1029. Median (25)-PAT甲级真题（two points）

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

Input

Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (<=1000000) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

Output

For each test case you should output the median of the two given sequences in a line.

Sample Input
4 11 12 13 14
5 9 10 15 16 17
Sample Output
13

题目大意：给出两个已排序序列，求这两个序列合并后的中间数

分析：既然两个数组都是递增的顺序，可以借助归并的思想~与归并排序不同的是，在第一个while里如果找到了中位数，就直接跳出来～
如果其中一个数组已经走到头也没有找到中位数，可以用数学公式直接推导出中位数在另一个数组中的位置～

PS：感谢@琦子块提供的更优解～

#include <iostream>
const int maxn = 200005;
int n, m, a1[maxn], a2[maxn], cnt = 0, i, j, ans;
int main() {
    scanf("%d", &n);
    for(i = 1; i <= n; i++) scanf("%d", &a1[i]);
    scanf("%d", &m);
    for(i = 1; i <= m; i++) scanf("%d", &a2[i]);
    int target = (n + m + 1) / 2;
    i = 1, j = 1;
    while(i <= n && j <= m) {
        ans = a1[i] <= a2[j] ? a1[i++] : a2[j++];
        if(++cnt == target) break;
    }
    if(i <= n && cnt < target)  
        ans = a1[i + target - cnt - 1];
    else if(j <= m && cnt < target) 
        ans = a2[j + target - cnt - 1];
    printf("%d", ans);
    return 0;
}

#include <iostream>

const int maxn = 200005;

int n, m, a1[maxn], a2[maxn], cnt = 0, i, j, ans;

int main() {

scanf("%d", &n);

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

scanf("%d", &m);

for(i = 1; i <= m; i++) scanf("%d", &a2[i]);

int target = (n + m + 1) / 2;

i = 1, j = 1;

while(i <= n && j <= m) {

ans = a1[i] <= a2[j] ? a1[i++] : a2[j++];

if(++cnt == target) break;

}

if(i <= n && cnt < target)

ans = a1[i + target - cnt - 1];

else if(j <= m && cnt < target)

ans = a2[j + target - cnt - 1];

printf("%d", ans);

return 0;

}

【Sublime】Mac下Sublime代码自动换行

Sublime -> Preferences -> Settings – User

Snip20160816_23

在里面添加一句 “word_wrap”: true
然后保存即可。

Snip20160816_24

【Sublime】Mac下使用Sublime编译运行带输入数据的程序

Sublime->Tools->Build System->New Build System…

Snip20160816_20

粘贴以下代码并保存为G++ Run in.sublime-build

{
	"cmd": ["bash", "-c", "g++ '${file}' -o '${file_path}/${file_base_name}' && '${file_path}/${file_base_name}' < in"]
}

{

"cmd": ["bash", "-c", "g++ '${file}' -o '${file_path}/${file_base_name}' && '${file_path}/${file_base_name}' < in"]

}

Snip20160816_21

在要编译运行的cpp程序的文件夹下新建保存一个名为“in”的文件，作为接收输入数据的文件

Snip20160816_19

然后在in文件里面输入输入数据并保存，打开需要编译运行的.cpp文件（要先保存为.cpp文件），按cmd+shift+B编译运行即可。

1115. Counting Nodes in a BST (30)-PAT甲级真题（二叉树的遍历，dfs）

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000) which is the size of the input sequence. Then given in the next line are the N integers in [-1000 1000] which are supposed to be inserted into an initially empty binary search tree.

Output Specification:

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format:

n1 + n2 = n

where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

Sample Input:
9
25 30 42 16 20 20 35 -5 28
Sample Output:
2 + 4 = 6

题目大意：输出一个二叉搜索树的最后两层结点个数a和b，以及他们的和c：“a + b = c”
分析：用链表存储，递归构建二叉搜索树，深度优先搜索，传入的参数为结点和当前结点的深度depth，如果当前结点为NULL就更新最大深度maxdepth的值并return，将每一层所对应的结点个数存储在数组num中，输出数组的最后两个的值～～

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int v;
    struct node *left, *right;
};
node* build(node *root, int v) {
    if(root == NULL) {
        root = new node();
        root->v = v;
        root->left = root->right = NULL;
    } else if(v <= root->v)
        root->left = build(root->left, v);
    else
        root->right = build(root->right, v);
    return root;
}
vector<int> num(1000);
int maxdepth = -1;
void dfs(node *root, int depth) {
    if(root == NULL) {
        maxdepth = max(depth, maxdepth);
        return ;
    }
    num[depth]++;
    dfs(root->left, depth + 1);
    dfs(root->right, depth + 1);
    
}
int main() {
    int n, t;
    scanf("%d", &n);
    node *root = NULL;
    for(int i = 0; i < n; i++) {
        scanf("%d", &t);
        root = build(root, t);
    }
    dfs(root, 0);
    printf("%d + %d = %d", num[maxdepth-1], num[maxdepth-2], num[maxdepth-1] + num[maxdepth-2]);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct node {

int v;

struct node *left, *right;

};

node* build(node *root, int v) {

if(root == NULL) {

root = new node();

root->v = v;

root->left = root->right = NULL;

} else if(v <= root->v)

root->left = build(root->left, v);

else

root->right = build(root->right, v);

return root;

}

vector<int> num(1000);

int maxdepth = -1;

void dfs(node *root, int depth) {

if(root == NULL) {

maxdepth = max(depth, maxdepth);

return ;

}

num[depth]++;

dfs(root->left, depth + 1);

dfs(root->right, depth + 1);

}

int main() {

int n, t;

scanf("%d", &n);

node *root = NULL;

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

scanf("%d", &t);

root = build(root, t);

}

dfs(root, 0);

printf("%d + %d = %d", num[maxdepth-1], num[maxdepth-2], num[maxdepth-1] + num[maxdepth-2]);

return 0;

}

1051. Pop Sequence (25)-PAT甲级真题（栈模拟）

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

Sample Input:
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2
Sample Output:
YES
NO
NO
YES
NO
题目大意：有个容量限制为m的栈，分别把1，2，3，…，n入栈,给出一个系列出栈顺序，问这些出栈顺序是否可能～
分析：按照要求进行模拟。先把输入的序列接收进数组v。然后按顺序1~n把数字进栈，每进入一个数字，判断有没有超过最大范围，超过了就break。如果没超过，设current = 1，从数组的第一个数字开始，看看是否与栈顶元素相等，while相等就一直弹出栈，不相等就继续按顺序把数字压入栈～～最后根据变量flag的bool值输出yes或者no～

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    int m, n, k;
    scanf("%d %d %d", &m, &n, &k);
    for(int i = 0; i < k; i++) {
        bool flag = false;
        stack<int> s;
        vector<int> v(n + 1);
        for(int j = 1; j <= n; j++)
            scanf("%d", &v[j]);
        int current = 1;
        for(int j = 1; j <= n; j++) {
            s.push(j);
            if(s.size() > m) break;
            while(!s.empty() && s.top() == v[current]) {
                s.pop();
                current++;
            }
        }
        if(current == n + 1) flag = true;
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

int main() {

int m, n, k;

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

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

bool flag = false;

stack<int> s;

vector<int> v(n + 1);

for(int j = 1; j <= n; j++)

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

int current = 1;

for(int j = 1; j <= n; j++) {

s.push(j);

if(s.size() > m) break;

while(!s.empty() && s.top() == v[current]) {

s.pop();

current++;

}

if(current == n + 1) flag = true;

if(flag) printf("YES\n");

else printf("NO\n");

}

return 0;

}