请问一下大佬们,我按照《算法竞赛进阶指南》上一道题的思路来仿照写这题,感觉也比较像正解中的“差分之后,相当于每次操作是选俩数,给左边的-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) 回帖