阿里笔试4.1场（附代码 + 3月全5场代码链接）

/*
把一个串恢复全0的最小步数 = 从全0变为该串的最小步数
对于某一个串，计算其1步可达的串，等价于其与7（二进制111）及其左移N位作异或
（注意收尾位的处理，我是单独处理手尾位，用3和3的左移串长-2位作异或）
如果新增串之前没有记录过，就记录其到0的距离是当前串+1，并将其加入处理队列
队列空，则所有可达串访问完毕。
如果访问到目标串，返回其步长，否则返回No
*/

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<math.h>

using namespace std;

int str2num(string s) {
    int res = s[0] - '0';
    int i;
    for(i = 1; i < s.length(); i++) {
        res = res*2 + s[i] - '0';
    }
    return res;
}

int fun(string s) {
    if(s.empty()) {
        return INT_MAX;
    }
    else if(s.length() == 1) {
        if(s[0] == '0') {
            return 0;
        }
        else {
            return INT_MAX;
        }
    }
    else if(s.length() == 2) {
        if(s[0] == s[1]) {
            return s[0] - '0';
        }
        else {
            return INT_MAX;
        }
    }
    
    int val = str2num(s);
    vector<int> mark;
    queue<int> pos;
    int i, tmp;
    for(i = 0; i < int(pow(2, s.length())); i++) {
        mark.push_back(INT_MAX);
    }
    mark[0] = 0;
    pos.push(0);
    
    int shiftv[s.length()];
    shiftv[0] = 3;
    for(i = 1; i < s.length()-1; i++) {
        shiftv[i] = 7<<(i-1);
    }
    shiftv[s.length()-1] = 3<<(s.length()-2);
    
    while(!pos.empty()) {
        for(i = 0; i < s.length(); i++) {
            tmp = pos.front()^shiftv[i];
            if(tmp == val) {
                return mark[pos.front()]+1;
            }
            else if(mark[tmp] == INT_MAX){
                mark[tmp] = mark[pos.front()]+1;
                pos.push(tmp);
            }
        }
        pos.pop();
    }
    return mark[val];
}

int main() {
    string s;
    cin>>s;
    int res = fun(s);
    if(res == INT_MAX) {
        cout<<"No"<<endl;
    }
    else {
        cout<<res<<endl;
    }
    return 0;
}

/*
 从左向右，如第i位碰到1时，反转第i,i+1,i+2位，直到完成完整串
 如果全部完成后，最后一位是1，表示不能翻转出全0；否则就返回翻转次数
 由于这种操作没有对同一位置的重复操作，一定是最少的
 时间复杂度O(n)
 */

/*
 补充：原代码没有考虑第一位需要翻转的情况，因此现在分别考虑第一位翻转和第一位不翻转两种情况，
 取两者中能够成功且次数小的一种。
*/

#include<iostream>
#include<string>
#include<math.h>

using namespace std;

int fun(string s) {
    if(s.empty()) {
        return 0;
    }
    
    int i;
    int count = 0;
    for(i = 0; i < s.length()-1; i++) {
        if(s[i] == '1') {
            s[i] = '0';
            s[i+1] = '0' + (1 - (s[i+1] - '0'));
            if(i < s.length() - 2) {
                s[i+2] = '0' + (1 - (s[i+2] - '0'));
            }
            count++;
        }
    }
    if(s[s.length()-1] == '1') {
        return INT_MAX;
    }
    else {
        return count;
    }
}

int main() {
    string s;
    cin>>s;
    int res = fun(s), res2;
    string scp;
    scp = s;
    if(s.length() > 2) {
        scp[0] = '0';
        scp[1] = '0' + (1 - (s[1] - '0'));
    }
    res2 = fun(scp);
    if(res2 != INT_MAX) {
        res = min(res, res2 + 1);
    }
    
    if(res == INT_MAX) {
        cout<<"NO"<<endl;
    }
    else {
        cout<<res<<endl;
    }
    return 0;
}

/*
1. 对怪兽生命从大到小排序
2. 对弓箭按攻击力从大到小排序
3. 建立一个优先队列，按照价值从小到大
之后按照顺序对每个怪兽计算:
 1.找出所有攻击力大于等于其生命值的弓箭，将其加入优先队列
 2.若此时队列空，证明没有可以消灭该怪兽的弓箭了，返回-1
   否则将优先队列队头出队，记录其价值。
 返回总价值即可。
时间复杂度O(mlogm)
*/

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct prs {
    int cost;
    int att;
};

bool cmp1 (int a, int b) {
    return a > b;
}

bool cmp2(prs p1, prs p2) {
    return p1.att > p2.att;
}

int mincost(vector<int> &monst,vector<prs> &arrow) {
    if(monst.size() > arrow.size()) {
        return -1;
    }
    sort(monst.begin(), monst.end(), cmp1);
    sort(arrow.begin(), arrow.end(), cmp2);
    priority_queue<int, vector<int>, greater<int> > pq;
    
    int res = 0;
    int i, j = 0;
    
    for(i = 0; i < monst.size(); i++) {
        while(j < arrow.size() && arrow[j].att >= monst[i]) {
            pq.push(arrow[j].cost);
            j++;
        }
        if(pq.empty()) {
            return -1;
        }
        else {
            res = res + pq.top();
            pq.pop();
        }
    }
    return res;
}

int main() {
    int N, M;
    cin>>N>>M;
    
    vector<int> monst;
    vector<prs> arrow;
    prs ptmp;
    int tmp;
    int i;
    
    for(i = 0; i < N; i++) {
        cin>>tmp;
        monst.push_back(tmp);
    }
    for(i = 0; i < M; i++) {
        cin>>ptmp.cost;
        arrow.push_back(ptmp);
    }
    for(i = 0; i < M; i++) {
        cin>>arrow[i].att;
    }
    
    cout<<mincost(monst, arrow)<<endl;
    return 0;
}