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();
}
} 