PAT甲级刷题记录-(AcWing)-Day16(贪心 3题 链表 4题 基础算法 3题)

PAT甲级刷题记录-(AcWing)-Day16(贪心 3题 链表 4题 基础算法 3题)

课程来源AcWing
其中AcWing中的题目为翻译好的中文题目
跳过了模拟的一些题和贪心的一些题,快考试了,先刷一下链表的和基础算法的

刷题列表

• PAT甲级刷题记录-(AcWing)-Day16(贪心 3题 链表 4题 基础算法 3题)
• • 1037 Magic Coupon
  • 1038 Recover the Smallest Number
  • 1067 Sort with Swap(0, i)
  • 1032 Sharing
  • 1097 Deduplication on a Linked List
  • 1074 Reversing Linked List
  • 1133 Splitting A Linked List
  • • vector.insert 方法
  • 1029 Median
  • 1046 Shortest Distance
  • 1085 Perfect Sequence

1037 Magic Coupon

AcWing链接
PAT链接

英语单词

• coupon 优惠券
• bonus product 赠品
  解析
  贪心的题目难在思路上(一般数量级在 1 0 5 左 右 10^5左右 105左右)
  本题设计到了排序不等式
  先将优惠券和商品价值分别排序
  针对正数和负数采用最大值与最大值配对的方式,得到最后的结果

注意点

#include 
#include 

const int N = 100010;
using namespace std;
int nc, np;
int a[N], b[N];

int main() {
    scanf("%d", &nc);
    for (int i = 0; i < nc; ++i) {
        scanf("%d", a + i);
    }
    scanf("%d", &np);
    for (int i = 0; i < np; ++i) {
        scanf("%d", b + i);
    }
    sort(a, a + nc, greater());
    sort(b, b + np, greater());
    long long res = 0;
    for (int i = 0, j = 0; i < nc && j < np && a[i] > 0 && b[j] > 0; ++i, ++j) {
        res += a[i] * b[j];
    }
    for (int i = nc - 1, j = np - 1; i >= 0 && j >= 0 && a[i] < 0 && b[j] < 0; --i, --j) {
        res += a[i] * b[j];
    }
    cout << res << endl;
    return 0;
}

1038 Recover the Smallest Number

AcWing链接
PAT链接

英语单词

解析
用a + b < b + a (ab < ba)来判断a和b两个字符串的前后位置
自定义排序的规则

注意点
c++ 中erase函数的三种用法

• erase( position); 删除position处的一个字符（position是个string类型的迭代器）

#include 
#include 

const int N = 10010;
using namespace std;
string num[N];
int n;

bool cmp(string &s1, string &s2) {
    return s1 + s2 < s2 + s1;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
    }

    sort(num, num + n, cmp);
    string res;
    for (int i = 0; i < n; ++i) {
        res += num[i];
    }
    int k = 0;
    while (k + 1 < res.size() && res[k] == '0') k++;
    res = res.substr(k);
    cout << res << endl;
    return 0;
}

1067 Sort with Swap(0, i)

AcWing链接
PAT链接

英语单词

解析
图论+自环的思思路解题
把每个位置和其所在的位置连一条有向边，最终构成的图一定是若干个环。
我们每次的操作都是将0和其它数进行交换

• 0和0所在的环里的数进行交换
  • 只将0和它的下一个数进行交换，这样就可以把下一个数转换为一个自环,也就是排序到了正确的位置
• 0和其它环里的数进行交换。
  • 0和外部环中的数进行交换时，将会是两个环连通。

所以，我们的操作是，先让0不断和环内的下一个节点交换,完成0所在环内所有数字的正确排序
然后将0与其他环的数字交换,完成环的联通
再重复上述操作
注意点

#include 
#include 

using namespace std;
const int N = 100010;
int num[N], n, pos[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        pos[num[i]] = i; // 记录当前数字应该在的正确位置
    }
    int res = 0;
    for (int i = 0; i < n;) {
        while (pos[0]) {
            // 完成0所在的环内的交换, 直到0变成自环
            swap(pos[0], pos[pos[0]]);
            res++;
        }
        while (i < n && pos[i] == i) {
            // 找到下一个要合并的环, 跳过所有是自环的点
            i++;
        }
        if (i < n) swap(pos[0], pos[i]), res++;
    }
    cout << res << endl;
    return 0;
}

1032 Sharing

AcWing链接
PAT链接
英语单词

解析

注意点

#include 
#include 
#include 

const int N = 100010;
using namespace std;
int h1, h2, ne[N];
char e[N];

int main() {
    int n;
    cin >> h1 >> h2 >> n;
    while (n--) {
        int address, next;
        char data;
        cin >> address >> data >> next;
        e[address] = data;
        ne[address] = next;
    }
    unordered_map res;
    for (int i = h1; i != -1; i = ne[i]) {
        res[i]++; // 将第一个链表中所有地址加入vector中
    }
    for (int i = h2; i != -1; i = ne[i]) {
        if (res.count(i)) {
            printf("%05d", i);
            return 0;
        }
    }
    puts("-1");
    return 0;
}

1097 Deduplication on a Linked List

AcWing链接
PAT链接

英语单词

解析

注意点

#include 
#include 

const int N = 100010;
using namespace std;
int h, ne[N], e[N];
bool st[N];

void print(vector x) {
    for (int i = 0; i < x.size(); ++i) {
        int address = x[i], data = e[x[i]];
        if (i == x.size() - 1) {
            printf("%05d %d -1n", address, data);
        }else {
            printf("%05d %d %05dn", address, data, x[i + 1]);
        }
    }
}

int main() {
    int n;
    cin >> h >> n;
    while (n--) {
        int address, key, next;
        cin >> address >> key >> next;
        e[address] = key;
        ne[address] = next;
    }
    vector res;
    vector drop_li;
    for (int i = h; i != -1; i = ne[i]) {
        int data = abs(e[i]);
        if (!st[data]) {
            st[data] = true;
            res.push_back(i); // 将地址插入进去
        } else {
            // data不是第一次出现了, 删除
            drop_li.push_back(i);
        }
    }
    // 输出
    print(res);
    print(drop_li);
    return 0;
}

1074 Reversing Linked List

AcWing链接
PAT链接

英语单词

解析

注意点
一开始看错题了, 是反转元素的值,我搞成排序了,然后竟然只错了一个测试点

这边代码不用那么麻烦, 反转的话在数组中只要记录元素的地址就好了,不用搞个哈希表来映射值和地址的关系

#include 
#include 
#include 
#include 

const int N = 100010;
using namespace std;
int n, h, k;
int ne[N], e[N];
unordered_map pos;

int main() {
    cin >> h >> n >> k;
    vector vec;
    while (n--) {
        int add, data, next;
        cin >> add >> data >> next;
        e[add] = data;
        ne[add] = next;
        pos[data] = add;
    }
    for (int i = h; ~i; i = ne[i]) {
        vec.push_back(e[i]);
    }
    for (int i = 0; i + k - 1 < vec.size(); i += k) {
        reverse(vec.begin() + i, vec.begin() + i + k);
    }
    for (int i = 0; i < vec.size(); ++i) {
        if (i == vec.size() - 1) printf("%05d %d -1n", pos[vec[i]], vec[i]);
        else printf("%05d %d %05dn", pos[vec[i]], vec[i], pos[vec[i + 1]]);
    }
    return 0;
}

1133 Splitting A Linked List

AcWing链接
PAT链接

英语单词

解析

vector.insert 方法

vector.insert(pos,elem);   //在pos位置插入一个elem元素的拷贝，返回新数据的位置。

vector.insert(pos,n,elem);   //在pos位置插入n个elem数据，无返回值。

vector.insert(pos,beg,end);   //在pos位置插入[beg,end)区间的数据，无返回值 

//将vec2插入到vec1尾部
vec1.insert(vec1.end(),vec2.begin(),vec2.end());

注意点

// 所有的负数出现在正数前面
// [0, K] 之间的元素出现在 大于k的元素之前
// 每一类元素直接的顺序不变
// 思路: 用三个数组来记录每个元素的地址, 然后按顺序输出就好了
#include 
#include 

using namespace std;
const int N = 100010;
int e[N], ne[N], h;
int n, k;

int main() {
    cin >> h >> n >> k;
    vector a, b, c;
    while (n--) {
        int address, data, next;
        cin >> address >> data >> next;
        e[address] = data;
        ne[address] = next;
    }
    for (int i = h; ~i; i = ne[i]) {
        if (e[i] < 0) a.push_back(i);
        else if (e[i] <= k) b.push_back(i);
        else c.push_back(i);
    }
    a.insert(a.end(), b.begin(), b.end());
    a.insert(a.end(), c.begin(), c.end());
    for (int i = 0; i < a.size(); ++i) {
        if (i == a.size() - 1) printf("%05d %d -1n", a[i], e[a[i]]);
        else printf("%05d %d %05dn", a[i], e[a[i]], a[i + 1]);
    }
    return 0;
}

1029 Median

AcWing链接
PAT链接

英语单词

解析

注意点
int target = (n + m - 1) / 2; 更方便

#include 
#include 
#include 
#include 
using namespace std;
const int N = 200010;
int a[N], b[N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", a + i);

    }
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d", b + i);
    }
    int target = round((n + m) * 1.0 / 2);
    int i = 0, j = 0;
    vector res;
    while (i < n&& j < m) {
        if (a[i] < b[j]) res.push_back(a[i++]);
        else res.push_back(b[j++]);
    }
    if (res.size() >= target) {
        printf("%dn", res[target - 1]);
    }else{
        while (i < n) res.push_back(a[i++]);
        while (j < m) res.push_back(b[j++]);
        printf("%dn", res[target - 1]);
    }
    return 0;
}

1046 Shortest Distance

AcWing链接
PAT链接

英语单词

解析
前缀和的应用

注意点

• s[1] 中存放的是 1-> 2的距离
• s[2] 中存放的是 1->2->3的距离
• s[k] 中存放的是 1 -> k+1 的距离
• s[n] - s[n-1] 中存放的是 n->1的距离

计算a到b的距离有两种方式,因为路线是个环

1. s[b-1] - s[a-1]
2. s[n] - s[b - 1] + s[a - 1]

#include 

using namespace std;
const int N = 100010;
int s[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    int m;
    cin >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        int dis = min(s[b - 1] - s[a - 1], s[n] - s[b - 1]  + s[a - 1]);
        printf("%dn", dis);
    }
    return 0;
}
//5 1 2 4 14 9
//3
//1 3
//2 5
//4 1

1085 Perfect Sequence

AcWing链接
PAT链接

英语单词

解析

注意点
经典的双指针
要注意这边a[i] * p 的范围可能会超过int,要转成long long

#include 
#include 

using namespace std;
const int N = 100010;
int n, p;
int a[N];

// M≤m×p
int main() {
    cin >> n >> p;
    for (int i = 0; i < n; ++i)cin >> a[i];
    int res = 0;
    sort(a, a + n);
    for (int i = 0, j = 0; i < n; ++i) {
        while ((long long)a[i] * p >= a[j] && j < n) {
            j++;
        }
        res = max(j - i ,res);
    }
    cout << res;
    return 0;
}
// 10 8
//2 3 20 4 5 1 6 7 8 9