竞赛讨论区 > C题求助呜呜
头像
ING__
编辑于 2022-01-21 08:33
+ 关注

C题求助呜呜

请问一下大佬们,我按照《算法竞赛进阶指南》上一道题的思路来仿照写这题,感觉也比较像正解中的“差分之后,相当于每次操作是选俩数,给左边的-1给右边的+1,那对于固定的左边那个数,肯定优先给离他最近的右边那个数+1最好”,可是却wa了,有没有大佬能帮我看一下😭😭😭,不胜感激

那题的思路:图片说明

这题修改后的思路:
在第一步的操作中两重循环来满足大于等于k的限制,最后再检查一下是不是能满足答案的要求,即差分数组b全为0

#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define re return
#define pb push_back
#define Endl "\n"
#define endl "\n"
#define x first
#define y second
#define all(x) (x).begin(),(x).end()

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;
const int M = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int T;
int n, k;
ll a[N];
ll b[N];

void solve(){
    vector<PII> res;

    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = __lg(a[i]);
    }

    for (int i = 1; i <= n; i++){
        b[i] = a[i] - a[i - 1];
        // cout << b[i] << ' ';
    }
    // cout << endl;


    for (int i = 2; i <= n; i++){
        for (int j = i + k; j <= n; j++){
            if(b[i] > 0 && b[j] < 0){
                int tmp = min(abs(b[i]), abs(b[j]));

                b[i] -= tmp;
                b[j] += tmp;

                while(tmp--)
                    res.pb({i, j - 1});
            }
        }
    }

    for (int i = 2; i <= n; i++){
        if(b[i] < 0 && b[1] > 0){
            if(i - 1 < k){
                cout << -1 << endl;
                return;
            }
            int tmp = min(b[1], abs(b[i]));
            b[i] += tmp;
            b[1] -= tmp;

            while(tmp--)
                res.pb({1, i - 1});
            // cout << 1 << ' ' << i - 1 << endl;
        }
        if(b[i] > 0){
            if(n - i + 1 < k){
                cout << -1 << endl;
                return;
            }
            b[i]--;
            res.pb({i, n});
        }
    }

     if(b[1] != 0){
        for (int i = 1; i <= b[1]; i++){
            res.pb({1, n});
        }
     }

     for (int i = 2; i <= n; i++){
         if(b[i] != 0){
             cout << -1 << endl;
             return;
         }
     }

     cout << res.size() << endl;
     for (auto i : res){
         cout << i.x << ' ' << i.y << endl;
    }
}

int main(){
    T = 1;
    cin >> T;
    while(T--){
        solve();
    }
}

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐