（二）贪心算法与哈夫曼树

https://vjudge.net/contest/145673#overview

– A – 简单-部分背包


很经典的暴力题目了

#include<iostream>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;
int n, m;
struct p{
    int v;
    int n;
}item[1005];

bool cmp(p a, p b){
    return a.v*b.n > b.v*a.n;
}

int main() {
    while (cin >> n >> m,n!=-1){
        for (int i = 0; i < m; i++){
            scanf("%d%d", &item[i].v, &item[i].n);
        }
        sort(item, item + m, cmp);
        double ans = 0;
        for (int i = 0; i < m; i++){
            if (n >= item[i].n){
                n -= item[i].n;
                ans += item[i].v;
            }
            else{
                ans += (double)item[i].v*n / item[i].n;
                break;
            }
        }
        cout << fixed << setprecision(3) << ans << endl;
    }
    return 0;
}

• 1

– B – 简单-选择不相交区间


也是很经典的暴力题，要求怎样选择电视节目使得看到的完整电视节目数量最多，只需要尽量选结束时间最早的就行了。

#include<iostream>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;
int n;
struct tv{
    int beg;
    int end;
}item[105];

bool cmp(tv a, tv b){
    return a.end < b.end;
}

int main() {
    while (cin >> n,n!=0){
        for (int i = 0; i < n; i++){
            scanf("%d%d", &item[i].beg, &item[i].end);
        }
        sort(item, item + n, cmp);
        int ans = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++){
            if (item[i].beg >= cnt){
                cnt = item[i].end;
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

• 1

– C – 简单-区间选点问题


要求求出最少的雷达使得所有小岛都被监视到，只需要求出对于每一个小岛能监视到他的雷达可以放置的最左端坐标和最右端坐标，然后多个小岛的雷达可放置区域重叠则在重叠区放置时得到最小值。

#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<stdio.h>
using namespace std;
int n,d,casenum;
struct point{
    int x;
    int y;
    double l;
    double r;
}p[1005];
bool v[1005];
bool cmp(point a, point b){
    return a.r < b.r;
}

int main() {
    casenum = 1;
    while (cin >> n>>d,n!=0){
        bool y = true;
        int dd = d*d;
        if (d < 0){ y = false; }
        for (int i = 0; i < n; i++){
            scanf("%d%d", &p[i].x, &p[i].y);
            double dist = sqrt(dd - p[i].y*p[i].y);
            p[i].l = p[i].x - dist, p[i].r = p[i].x + dist;
            if (p[i].y>d || p[i].y<0){ y = false; }
        }
        getchar();
        getchar();
        printf("Case %d: ", casenum++);
        if (y == false){
            printf("%d\n", -1);
        }
        else{
            sort(p, p + n, cmp);
            int ans = n;
            double cnt;
            for (int i = 0; i < n; i++){
                cnt = p[i].r;
                while (p[++i].l <= cnt&&i<n){
                    ans--;
                }
                i--;
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

• 1

– D – 简单-哈夫曼编码


给出一个字符串，要求求出用等长8bit保存所需的长度和使用哈夫曼编码所需的编码长度以及它们的比值。（以前只懂得手动画哈夫曼树，都不懂的怎么用代码算）使用了优先级队列来模拟，每次合并分支得到的值加到ans里可以求得huffman所需的编码长度。

#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<map>
#include<queue>
using namespace std;
string str;
struct num{
    int n;
    bool operator < (const num &b)const{
        return n > b.n;
    }
};
num word[27];
priority_queue<num> que;
int main() {
    while (cin >> str, str != "END"){
        while (!que.empty()){
            que.pop();
        }
        int len = str.length();
        for (int i = 0; i < 27; i++){
            word[i].n = 0;
        }
        for (int i = 0; i < len; i++){
            if (str[i] == '_'){ word[0].n++; }
            else{ word[str[i] - 'A' + 1].n++; }
        }
        for (int i = 0; i < 27; i++){
            if (word[i].n != 0){ que.push(word[i]); }
        }
        int ans = 0;
        if (que.size() == 1){ ans = len; }
        else{
            while (que.size()>1){
                num a = que.top();
                que.pop();
                num b = que.top();
                que.pop();
                ans += a.n + b.n;
                que.push({ a.n + b.n });
            }
        }
        double r2 = len * 8 / double(ans);
        printf("%d %d %.1f\n", len * 8, ans, double(len * 8) / ans);
    }
    return 0;
}

• 1

– E – 简单-应用1


给出一串长度为n的数字序列，要求你用最少替换次数把它变成1-n的不重复序列。被替换掉的数字肯定是重复出现或者大于n的数字，所以先遍历一遍，把没出现的数字存到数组中，然而第二次遍历把重复出现或大于范围的数字替换成数组中的。

#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
using namespace std;
bool biao[100005];
int zhan[100005];
bool biao2[100005];
int num[100005];
int n, account;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &num[i]);
    }
    for (int i = 0; i < n; i++){
        biao[num[i]] = true;
    }
    for (int i = 1; i <= n; i++){
        if (biao[i] == false){
            zhan[account++] = i;
        }
    }
    account = 0;
    for (int i = 0; i < n; i++){
        if (num[i]>n || biao2[num[i]] == true){
            num[i] = zhan[account++];
        }
        else{ biao2[num[i]] = true; }
    }
    for (int i = 0; i < n; i++){
        printf("%d", num[i]);
        if (i < n - 1)putchar(' ');
    }

    return 0;
}

• 1

– F – 困难-应用2


第一棵树固定往左倒，最后一颗树固定往右倒，然后从左往右，对每棵树先看能不能往左倒，再看能不能往右倒，能到就让它倒下，（一棵树能倒下你却让它不倒而把空间让给后面的并不会让答案树增加）

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int n, ans;
int x[100005];
int h[100005];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d%d", &x[i], &h[i]);
    }
    ans = 2;
    for (int i = 1; i < n - 1; i++){
        if (x[i - 1] < x[i] - h[i]){
            ans++;
        }
        else if (x[i + 1]>x[i] + h[i]){
            x[i] = x[i] + h[i];
            ans++;
        }
    }
    if (n == 1){ ans = 1; }
    printf("%d", ans);

        return 0;
}

• 1

– G – 中等-应用3


很强的一道题，按照每本书第一次出现的次序排书可以得到正确答案，模拟取书的方法也很精妙，反正我看到题解前时想不到这样的解法的。

#include<iostream>
#include<string>
#include<iomanip>
#include<stdio.h>
using namespace std;
int n, m, ans;
int w[505], b[1005];
bool v[505];
int main()
{
    ans = 0;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int i = 1; i <= m; i++)
        scanf("%d", &b[i]);
    for (int i = 2; i <= m; i++)
    {
        memset(v, 0, sizeof(v));
        for (int j = i - 1; j >= 0; j--){
            if (b[i] == b[j]){ break; }
            if (!v[b[j]]){
                ans += w[b[j]];
                v[b[j]] = 1;
            }
        }
    }
        printf("%d", ans);

        return 0;
}

• 1

– H – 中等-应用4


拆玩具，每次拆需要的能量为与之相连的部分的值，从值最大的递减拆能得到最小能量消耗。

#include<iostream>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<vector>
using namespace std;
int n, m, ans;
struct th{
    int v;
    int n;
}t[1005];
bool vis[1005];
int v[1005];
vector<int> e[1005];
bool cmp(th a, th b){
    return a.v > b.v;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++){
        scanf("%d", &t[i].v);
        t[i].n = i+1;
        v[i + 1] = t[i].v;
    }
    int x, y;
    for (int i = 0; i < m; i++){
        scanf("%d%d", &x, &y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    sort(t, t + n, cmp);
    for (int i = 0; i < n-1; i++){
        int cnt = t[i].n;
        int len = e[cnt].size();
        for (int j = 0; j < len; j++){
            if (!vis[e[cnt][j]]){
                ans += v[e[cnt][j]];
            }
        }
        vis[t[i].n] = 1;
    }
    printf("%d", ans);

        return 0;
}

• 1

– I – 困难-应用5


排序+dp，考虑到正解肯定一个解题序列，答案的解题序列确定了哪些题要解，肯定时唯一的顺序，考虑相邻的两道题交换顺序并不会对之前和之后的题目有影响，所以只需要所需时间/衰减速度大的排在前面就行了，然后dp即可。

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
struct prob{
    long long maxp, ppm, rqt;
}problem[1005];
long long dp[3005];
int n, tim;
bool cmp1(prob a, prob b){
    if (a.rqt*b.ppm == b.rqt* a.ppm){
        return a.ppm > b.ppm;
    }
    return a.rqt*b.ppm < b.rqt* a.ppm;
}
long long max(long long a, long long b){
    return a > b ? a : b;
}
int main(){
    int t;
    cin >> t;
    while (t--){
        memset(dp, 0, sizeof(dp));
        cin >> n >> tim;
        for (int i = 0; i < n; i++){
            cin >> problem[i].maxp >> problem[i].ppm >> problem[i].rqt;
        }
        sort(problem, problem + n, cmp1);
        for (int i = 0; i < n; i++){
            for (int j = tim; j >= problem[i].rqt; j--){
                dp[j] = max(dp[j], dp[j - problem[i].rqt] + (problem[i].maxp - (j*problem[i].ppm)));
            }
        }
        long long res = 0;
        for (int j = 0; j <= tim; j++){
            if (dp[j]>res){ res = dp[j]; }
        }
        cout << res << endl;
    }
    return 0;
}