【题解】 —算法竞赛入门经典第二版 【第八章习题】【7/28】

UVa 1149 Bin Packing【贪心】

题目大意：

给定$N$个物品的重量$L_i$，背包的容量$M$，同时要求每个背包最多装两个物品，求至少需要多少个背包才能装下所有物品。

解题思路：

典型的贪心问题求解，排序后从两头取就可以了。

MyCode：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1e5+5;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int a[MAX];
int t, n, m, tot;
int main()
{
    cin >> t;
    while(t--)
    {
        tot = 0;
        cin >> n >> m;
        for(int i = 0; i < n; ++i)
            cin >> a[i];
        sort(a, a+n);
        int l = 0, r = n-1;
        while(l <= r)
        {
            if(l == r)  {++tot; break;}
            if(a[l] + a[r] <= m) ++l;
            ++tot;
            --r;
        }
        cout << tot << endl;
        if(t)   puts("");
    }
    return 0;
}

UVa 1610 Party Games【贪心】

题目大意：

给出$n$($n$为偶数)个字符串，要求你构造一个字符串，使得它的字典序恰好大于等于其中的一半，小于另一半，找到满足条件的长度最短的。

解题思路：

题意简化一下就是排序后，找出中间那两个字符串，对它们进行操作就可以了。

因为要求尽量短，所以首先想到的是从前往后遍历，找到第一个字母不同的位置，若两者差距 > $1$则可直接输出前 + $1$然后跳出。这个思路总体方向是正确的，但是是有漏洞的，比如此位置正好是小的那个字符串的最后一个位置？此位置正好是大的那个字符串的最后一个位置？处理完这两种情况后再考虑差距等于$1$的时候，这时直接输出小的字符串+$1$，同样的这时候也考虑当前位置是否为两字符串的末尾位置。

还有种思路是考虑两者的长度关系，设小的字符串为$u$，大的字符串为$v$。当u.size() <= v.size()的时候从前往后找，找到第一个不同的位置，当此位置==u.size()时直接输出$u$，否则输出$u[i] + 1$。剩下的一种情况时，也需要从前往后找到第一个不同的位置，当此位置==v.size()且v[i] - u[i] == 1时继续向后遍历$u$，直到找到$u$的结尾或者u[j] != 'Z'的位置，否则输出$u[i] + 1$。

MyCode：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 1005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int n;
string s[MAX];
string fr, en, ans;

string solve(string a, string b)
{
    string res = "";

    int en = a.size() - 1;
    int len = min(a.size(), b.size());
    for(int i = 0; i < len; ++i)
    {
        if(a[i] == b[i])
            res += a[i];
        else
        {
            if(i == en)
                res += a[i];
            else if(i != b.size() - 1 || b[i] - a[i] > 1)
                res += a[i]+1;
            else
            {
                res += a[i];
                for(int j = i+1; j < a.size(); ++j)
                {
                    if(j == en)
                    {
                        res += a[j];
                        break;
                    }
                    if(a[j] != 'Z')
                    {
                        res += a[j]+1;
                        break;
                    }
                    res += 'Z';
                }
            }
            break;
        }
    }
    return res;
}
int main()
{
    while(cin >> n && n)
    {
        for(int i = 0; i < n; ++i)
            cin >> s[i];
        sort(s, s+n);
        fr = s[n/2-1];
        en = s[n/2];
        ans = solve(fr, en);
        cout << ans << endl;
    }
    return 0;
}

UVa 12545 Bits Equalizer【贪心】

题目大意：

给出两个等长的字符串S和T，S包括0、1和?，T只包括0和1，要求你通过对S下列变换，经过尽量少的次数将S转换为T。

操作共有3种：1. 把0变为1。 2. 把?变为0或1。 3. 将任意两个字符交换位置。

解题思路：

1. 先看变不成的情况：$1_s > 1_t$，因为$1$是无法改变的。
2. 其余情况看如何变化使得操作数最小：由变换规则知，先把匹配位置的? -> 1再把0 -> 1是最优的。之后再把?变为0，不匹配的位置统计一下进行交换就好了。

MyCode：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

string s, t;
int _, res, now;
int main()
{
    scanf("%d",&_);
    for(int cas = 1; cas <= _; ++cas)
    {
        res = 0;
        cin >> s >> t;

        for(int i = 0; i < s.size(); ++i)
            if(s[i] == t[i])
                s[i] = t[i] = '*';

//        cout << s << endl << t << endl;

        int ones = 0, onet = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] == '1') ++ones;
            if(t[i] == '1') ++onet;
        }

        bool flag = ones > onet;    //s中的1比t中的1多
        if(flag)
            res = -1;
        else
        {
            int o = onet - ones;
            res += o;
//            cout << o << endl;

            now = 0;
            //优先让? -> 1
            for(int i = 0; i < s.size(); ++i)
            {
                if(now == o)    break;
                if(t[i] == '1' && s[i] == '?')
                {
                    s[i] = t[i] = '*';
                    ++now;
                }
            }
            //再考虑让 0 -> 1
            for(int i = 0; i < s.size(); ++i)
            {
                if(now == o)    break;
                if(t[i] == '1')
                {
                    s[i] = t[i] = '*';
                    ++now;
                }
            }

//            cout << s << endl << t <<endl;

            for(int i = 0; i < s.size(); ++i)
            {
                if(s[i] == '?')
                {
                    s[i] = '0';
                    ++res;
                }
            }

            now = 0;
            for(int i = 0; i < s.size(); ++i)
                if(s[i] != t[i])
                    ++now;

//            cout << s << endl << t <<endl;
//            cout << "now=" << now << endl;

            res += now / 2;
        }
        printf("Case %d: %d\n", cas, res);
    }
    return 0;
}

UVa 11491 Erasing and Winning【贪心】

题目大意：

给出一个$n$位整数，要求从中删除$d$位后得到的数的值尽量大。

解题思路：

每次删的时候都看一下删掉此位置的数后是否使得整体变大了，如果变大了就删了继续看，否则就往后找。当整个序列都是降序时就把最后几位删了。

MyCode：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int n, d;
string s;
void solve()
{
    int now = 0;
    while(s.size() > n)
    {
        bool f = 1;
        for(int i = now; i < s.size(); ++i)
        {
            if(s[i] < s[i + 1])
            {
                s.erase(s.begin() + i);
                now = i - 1 > 0 ? i - 1 : 0;
                f = 0;
                break;
            }
        }
        if(f)
        {
            s.erase(n, s.size() - n);
            break;
        }
    }
}
int main()
{
    while(cin >> n >> d && (n + d))
    {
        cin >> s;
        n -= d;
        solve();
        cout << s << '\n';
    }
    return 0;
}

UVa 177 Paper Folding【模拟】【规律】【未完成】

题目大意：

将一张纸从右向左进行对折$n$次，每次都打开“一半”，即把每个痕迹做成一个直角，输出打开后的图案。

解题思路：

写出前几种情况后观察发现，每次对折展开后比上次对了恰好一倍的线段数。而且多的那部分前一半刚好与原有的一半相反，后一半与原有的一半相同。然后根据这个规律可将所有的步数计算出来，然后选个中心按照步骤模拟就好了。

MyCode：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

char stp[1<<13 + 5];    /// 1 ~ 2^13 为每步走的位置
char mapa[1<<13][1<<13];
char opp(char ch)
{
    if(ch == 'r')   return 'l';
    if(ch == 'l')   return 'r';
    if(ch == 'u')   return 'd';
    if(ch == 'd')   return 'u';
}

void init()
{
    int idx = 3;
    stp[1] = 'r';
    stp[2] = 'u';
    for(int i = 1; i < 13; ++i)
    {
        ///要增加的位数
        int tot = 1 << i;
        ///改变的位数
        for(int j = 1; j <= tot / 2; ++j)
        {
            stp[idx] = opp(stp[idx - tot]);
            ++idx;
        }
        ///不变的位数
        for(int j = 1; j <= tot / 2; ++j)
        {
            stp[idx] = stp[idx - tot];
            ++idx;
        }
    }
    /*
    cout << idx << ' ' << (1 << 13) << '\n';
    for(int i = 1; i <= 16; ++i)
        cout << stp[i];
    cout << '\n';
    */
}

void draw()
{

}

int n;
void pint()
{

}

int main()
{
    init();
    draw();
    while(scanf("%d", &n) && n)
        pint();
    return 0;
}

UVa 1611 Crane【构造】【贪心】

题目大意：

输入一个$1$ ~ $n$的排列，用不超过$9^6$次操作把它变成升序。每次操作可以选择一个长度为偶数的连续区间，将它的前一半和后一半进行交换。

解题思路：

看到提示说只要$2n$次操作就够了，也就是说每个元素最多交换两次就可以到达它应到的位置。

具体操作是从一个方向开始，对于每一个位置找此位置的元素所在位置并将其交换过来，交换过来后就不用考虑这个位置了，继续往后看。这是还面临一个问题，就是区间长度为奇数时，这时需要多一次交换操作，将其交换到偶数位置处。

MyCode：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int a[MAX], b[MAX<<1], c[MAX<<1];
int t, n, idx, res, now, tem, tot;

void mmove(int st, int en)  //起点和终点
{
    int mid = (st + en + 1) / 2;
    int i, j;
    for(i = st, j = mid; j <= en; ++i, ++j)
        swap(a[i], a[j]);
    b[tot] = st;
    c[tot] = en;
    ++tot;
}

void movee(int st1, int st2)  //起点和起点
{
    int i, j;
    for(i = st1, j = st2; i < st2; ++i, ++j)
        swap(a[i], a[j]);
    int mid = st2 - st1 - 1;
    b[tot] = st1;
    c[tot] = st2 + mid;
    ++tot;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        tot = 0;
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
        for(int i = 1; i <= n; ++i)
        {
            while(a[i] != i)
            {
                for(int j = i+1; ; ++j) if(a[j] == i) {idx = j; break;}

                if(idx - i > n - idx && idx - i != 1)
                {
                    if((idx - i) & 1)
                        mmove(i, idx);
                    else
                        mmove(i+1, idx);

                    movee(i, i + (idx-i)/2);
                }
                else
                    movee(i, idx);
            }
        }

        printf("%d\n", tot);
        for(int i = 0; i < tot; ++i)
            printf("%d %d\n", b[i], c[i]);
    }
    return 0;
}

UVa 11925 Generating Permutations【】

题目大意：

给出一个$1$ ~ $n$的排列，用不到$2n^2$次操作把它$1$ ~ $n$的排列变为给出的排列。操作只有两种：交换前两个元素(操作1)；把第一个元素移动到最后(操作2)。

解题思路：

这题直接做不太好想，可以反着看，即将给的排列通过若干次操作转化为$1$ ~ $n$的排列。这样答案就是转换后的次序的逆转。

MyCode：

UVa 1612 【】

题目大意：

解题思路：

MyCode：

UVa 1613 【】

题目大意：

解题思路：

MyCode：

UVa 1614 Hell on the Markets【结论】【贪心】

题目大意：

输入一个长度为$n$的序列$a$，满足$1$ ≤ $a_i$ ≤ $i$，要求确定每个数的正负号，使得所有的数的总和为$0$。

解题思路：

结论：序列中的$a_i$满足$1 \leq a_i \leq i$，所以$1$ ~ $sum[i]$中的每个数都可用序列中的若干个数的和表示。

做法：将所有数从大到小排序，然后挨个取，同时记录当前取的数的和，当和$\leq 0$时就加上此位置的数，否则则减去。

MyCode：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100010;

int n, sum;
bool res[N];
struct node
{
    int val, idx;
} a[N];
bool cmp(node u, node v)
{
    return u.val > v.val;
}
int main()
{
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n; ++i)
        {
            a[i].idx = i;
            scanf("%d", &a[i].val);
        }
        sort(a + 1, a + 1 + n, cmp);
        sum = a[1].val;
        res[a[1].idx] = 0;
        for(int i = 2; i <= n; ++i)
        {
            if(sum > 0)
            {
                sum -= a[i].val;
                res[a[i].idx] = 1;
            }
            else
            {
                sum += a[i].val;
                res[a[i].idx] = 0;
            }
        }
        if(sum == 0)
        {
            puts("Yes");
            for(int i = 1; i <= n; ++i)
                printf("%d%c", res[i] ? -1 : 1, i == n ? '\n': ' ');
        }
        else
            puts("No");
    }
    return 0;
}

UVa 1615【】

题目大意：

解题思路：

MyCode：

UVa 1153 Keep the Customer Satisfied【贪心】【优先队列】

题目大意：

给出$n$个工作的需要时间和截止时间，问串行完成工作时最多能完成多少工作。

解题思路：

先按照截止日期从小到大排序，再按照需要时间从小到大排序，这样从前往后遍历，如果在规定时间内可以完成此任务，则将其存起来，否则和之前存的任务相比，如果之前的任务存在花费时间大于此任务的话，则删掉那个任务并替换为这个任务。不断进行此过程可以保证解是最优的。

MyCode：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 800000+5;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int t, n;

struct node
{
    int ned, date;
}a[MAX];

bool cmp(node u, node v)
{
    return u.date == v.date ? u.ned < v.ned : u.date < v.date;
}

int main()
{
    cin >> t;
    for(int cas = 0; cas < t; ++cas)
    {
        if(cas) puts("");

        cin >> n;
        for(int i = 0; i < n; ++i)
            cin >> a[i].ned >> a[i].date;
        sort(a, a+n, cmp);

        int t = 0;
        priority_queue <int> Q; //大的在前
        for(int i = 0; i < n; ++i)
        {
            if(t + a[i].ned <= a[i].date)
            {
                t += a[i].ned;
                Q.push(a[i].ned);
            }
            else if(Q.size())
            {
                if((a[i].ned < Q.top()) && (t + a[i].ned - Q.top() <= a[i].date))
                {
                    t -= Q.top();
                    Q.pop();
                    t += a[i].ned;
                    Q.push(a[i].ned);
                }
            }
        }
        cout << Q.size() << endl;
    }
    return 0;
}

UVa 10570 Meeting with Aliens【】

题目大意：

给出$1$ ~ $n$的一个环状排列，每次可以交换两个整数，用最少的次数将排列变成$1$ ~ $n$。输出最小次数。

解题思路：

MyCode：

UVa 1616【】

题目大意：

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：

UVa 1619 Feel Good【单调栈】

题目大意：

给出一个长为$n$的正整数序列，求出一段连续子序列$a_l, \dots, a_r$，使得$(a_l + \dots + a_r)$ $\times$ $min{a_l, \dots, a_r}$最大。

解题思路：

拓展：

存在负数情况时：https://nanti.jisuanke.com/t/38228

MyCode：

UVa 1312 Cricket Field【】

题目大意：

在一个$W$ * $H(1 \leq W,H \leq 10000)$的网格里有$n(0 \leq n \leq 100)$棵树，要求找一个最大的空正方形。

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：

UVa 【】

题目大意：

解题思路：

MyCode：