贪心 HDOJ 5355 Cake

时间:2025-03-03 14:33:26

好的,数据加强了,wa了

题目传送门

 /*
题意:1到n分成m组,每组和相等
贪心:先判断明显不符合的情况,否则肯定有解(可能数据弱?)。贪心的思路是按照当前的最大值来取
如果最大值大于所需要的数字,那么去找没有vis的数字
*/
/************************************************
* Author :Running_Time
* Created Time :2015-8-6 13:24:55
* File Name :C.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = 1e5 + ;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + ;
bool vis[MAXN];
vector<int> ans[];
ll n, m; int main(void) { //HDOJ 5355 Cake
int T; scanf ("%d", &T);
while (T--) {
memset (vis, false, sizeof (vis));
scanf ("%I64d%I64d", &n, &m);
ll tot = n * (n + ) / ;
if (tot % m != || tot / m < n) {
puts ("NO"); continue;
} ll sum = tot / m; ll mx = n;
for (int i=; i<=m; ++i) {
ans[i].clear (); ll tmp = sum;
while (tmp >= mx) {
tmp -= mx; ans[i].push_back (mx); vis[mx] = true;
while (mx - >= && vis[mx]) --mx;
}
ll t = mx;
while (tmp != ) {
while ((t - >= && vis[t]) || tmp < t) t--;
tmp -= t; ans[i].push_back (t); vis[t] = true;
t = tmp;
}
} puts ("YES");
for (int i=; i<=m; ++i) {
printf ("%d", (int) ans[i].size ());
for (int j=; j<ans[i].size (); ++j) {
printf (" %d", ans[i][j]);
}
puts ("");
}
} return ;
}