拼多多3.20笔试

1. 两个数组a和b，可以任意交换数组内元素位置，使得sum(ai-bi)最小

签到题，sort一下两个数组，直接求sum，结果比较大，会爆int

2. 有n片瓜田，第i片瓜田在[ai, bi]时间段内可以结ki个瓜，只能在这个时间段内去摘瓜，且每天总共只能摘v个瓜，问最多能摘多少个瓜

把瓜田按照b、a、k的优先级排序，然后枚举天数j，每天再从满足条件的瓜田里摘瓜。

凭记忆重写了一份代码，应该没问题……

（开始是用的枚举瓜田，然后一直卡在10%，后面找了很久错误样例，终于找到了原因）

（第一次写题解记错了排序的优先级顺序，不好意思........）

#include<bits/stdc++.h>
using namespace std;
#define LL long long
struct Watermelon{
    int k,a,b;
}watermelon[3100];

bool cmp(Watermelon w1, Watermelon w2){
    if(w1.b==w2.b){
        if(w1.a==w2.a)
            return w1.k<w2.k;
        return w1.a<w2.a;
    }
    return w1.b<w2.b;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        int n, v;
        cin>>n>>v;
        int st = INT_MAX, ed = INT_MIN;
        for(int i=0;i<n;i++){
            cin>>watermelon[i].k>>watermelon[i].a>>watermelon[i].b;
            st = min(st, watermelon[i].a);
            ed = max(ed, watermelon[i].b);
        }
        sort(watermelon, watermelon+n, cmp);
        LL ans = 0;
        int capacity = v;
        for(int i=st;i<=ed;i++){
            capacity = v;
            for(int j=0;j<n&&capacity;j++){
                if(i>=watermelon[j].a&&i<=watermelon[j].b&&watermelon[j].k){
                    int watermelon_cnt = min(capacity, watermelon[j].k);
                    ans+=watermelon_cnt;
                    capacity-=watermelon_cnt;
                    watermelon[j].k-=watermelon_cnt;
//                    cout<<ans<<endl;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

3. 两个只包含01的串a和b，输入整数k，b[i] = a[i-k] | a[i+k]，现在给定b和k，要求还原a，因为a可能有很多，输入字典序最小的那一个

a[i+k] = b[i] @ a[i-k]

0 0 0

1 1 0

1 1 1

0 1 1

可以看出前两种情况都是可以求出确定的a[i+k]的，同理

a[i-k] = b[i] @ a[i+k]

0 0 0

1 1 0

1 1 1

0 1 1

所以前后遍历两次，可以求出一部分的a[i+k]和a[i-k]值

当时做到这里，就加了个dfs，TLE了

T了之后又想到可以把遍历到的第一个不确定值设为0，然后继续上述操作，直到所有值都被找到。

（唯一本地还存着的代码，我这里用a[i]=2表示a[i]还未确定）

#include<bits/stdc++.h>
using namespace std;
#define LL long long

bool check(string a){

    for(int i=0;i<a.size();i++){
        if(a[i]=='2')
            return false;
    }
    return true;
}

string fun(string a, string b, int k){
    for(int i=0;i+k<b.size();i++){
        if(i-k<0){
            if(i+k<a.size())
                a[i+k]=b[i];
        }
        else if(a[i-k]=='0'&&b[i]=='0')
            a[i+k]='0';
        else if(a[i-k]=='0'&&b[i]=='1')
            a[i+k]='1';
    }
    for(int i=a.size()-1;i-k>=0;i--){
        if(i+k>=a.size()){
            if(i-k>=0)
                a[i-k]=b[i];
        }
        else if(a[i+k]=='0'&&b[i]=='0')
            a[i-k]='0';
        else if(a[i+k]=='0'&&b[i]=='1')
            a[i-k]='1';
    }
    return a;
}

int main(){
    int k;
    string b;
    cin>>k;
    cin>>b;
    string a(b.size(),'2');
    while(!check(a)){
        a = fun(a,b,k);
        for(int i=0;i<a.size();i++){
            if(a[i]=='2'){
                a[i]='0';
                break;
            }
        }
    }
    cout<<a<<endl;
    return 0;
}