P6775 [NOI2020]制作菜品
loveJY
·
·
题解
其实这题数据没有卡O(TnMaxV)也能过...
首先我们思考m>=n-1的情况,你会发现因为我们每次至多选择两个菜来做,再加上\sum是等于mk的,所以一定会有解,可以用贪心来做
无解当且仅当存在了多与两个材料他们才能拼成一道菜,而m=n-1的时候,我们每一步都一定能消除掉一个材料所以我们一定能最后都用光
那么当m>n的时候其实也是一样的,就是我们先用一个材料白做掉几个菜,然后一定能转化成m=n-1的情况那么也一定有解
然后再看m=n-2,说说非官方的考场思考过程:
$m=n-2$的时候可不可以认为我们能有两次一下消掉两个材料呢?
也就是说一个大的材料和其他许多的小的凑成正好好几道菜
会发现这是很可的!也就是说我们如果能先操作一下消掉一个材料,剩下的就是$m=n-1$的情况了!
所以这个就是很背包了,我们设(k-小于k的材料质量)为物品,目标就是去(凑成大于k的材料的质量)
如果能凑成,用所有小的材料和大的材料去结合做菜就一定能消掉一个环
剩下的材料丢给$m=n-1$算法解决
笔者m=n-1的算法是用的经典贪心:全局最小的和他能匹配的最小的材料做菜
**然而仔细想想,我们会挂在两个小材料凑成k这一个情况上**~~笔者因此考场挂掉了最小的三个点~~
但其实特判一下就好了....直接搞下即可
没有除以欧米伽的关键可能在于使用滚动数组来输出方案....才能开的下空间,可以看看下面代码实现的细节
而且空circle运算效率是真的快.....真就1s接近1e10啊?
当然要卡是能卡的,应该是k开满,然后用两个1e6级别的大材料吧?
code:
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
const int MAXN = 1e5 + 7;
const int MAXV = 2e6 + 6e5 + 7;
#define ins insert
#define mkp(x,y) (make_pair(x,y))
#define se second
#define fi first
int T, n, m, k;
using namespace std;
multiset<pair<int, int> > st;
struct rec {
int w, id;
bool operator<(const rec &x) const {
return w < x.w;
}
} d[MAXN];
struct AnS {
int x, y, z, w;
AnS(int x = 0, int y = 0, int z = 0, int w = 0): x(x), y(y), z(z), w(w) {};
} ans[MAXN];
int tot = 0, wp = 0, flg = 0, nw, M, ccnt;
int dp[MAXV], pos[MAXV], vis[MAXV], V[MAXV], bck[MAXV];
pair<int, int> que[MAXN];
inline void init() {
wp = tot = 0;
memset(dp, 0, sizeof(dp));
memset(V, 0, sizeof(V));
memset(bck, 0, sizeof(bck));
memset(vis, 0, sizeof(vis));
memset(pos, 0, sizeof(pos));
}
inline void solve() {//这个判断是O(mlogn)的....QAQ
st.clear();
for(int i = 1; i <= n; ++i) {
if(!vis[i]) {
st.ins(mkp(d[i].w, d[i].id));
}
}
for(int i = 1; i <= m; ++i) {
auto it = st.begin();
if((*it).fi >= k) {
ans[++tot] = AnS((*it).se, k);
st.erase(it);
if((*it).fi - k >= 0) {
st.ins(mkp((*it).fi - k, (*it).se));
}
} else {
auto it2 = st.lower_bound(mkp(k - (*it).fi, 0));
if(it == it2)++it2;
int x = (*it2).fi - (k - (*it).fi);
if(it != it2) {
ans[++tot] = AnS((*it).se, (*it).fi, (*it2).se, (k - (*it).fi));
st.erase(it);
st.erase(it2);
if(x)
st.ins(mkp(x, (*it2).se));
}//有点麻烦,nm的也可以....
}
}
for(int i = 1; i <= tot; ++i) {
if(ans[i].z)
printf("%d %d %d %d\n", ans[i].x, ans[i].y, ans[i].z, ans[i].w);
else printf("%d %d\n", ans[i].x, ans[i].y);
}
return ;
}
inline void solve2() {
sort(d + 1, d + n + 1);
M = k;
for(int i = 1; i <= n; ++i) {
if(d[i].w < k) {
que[++wp] = mkp(k - d[i].w, i);
} else if(d[i].w == k) {
ans[++tot] = AnS(i, k);
} else if(d[i].w > k) {
pos[d[i].w] = i;
M = max(d[i].w, M);
}//判断物品和M
}
pos[k] = 1;
nw = 0;
int rc = 0;
dp[0] = 1;
for(int i = 1; (i <= wp && !nw); ++i) {
for(int j = M; j >= que[i].fi; --j) {
//滚动数组输出方案只需要回跳就好了
//我们只有nt次更新,其他的都是空circle!
if(dp[j - que[i].fi] && !dp[j]) {
dp[j] = 1;
bck[j] = j - que[i].fi;
V[j] = que[i].se;
if(pos[j]) {
nw = j;
rc = pos[j];
break;
}
}
}
}
if(!nw)return (void)puts("-1");
if(nw == k) {//特判
vis[V[nw]] = 1;
printf("%d %d ", d[V[nw]].id, d[V[nw]].w);
nw = bck[nw];
vis[V[nw]] = 1;
printf("%d %d\n", d[V[nw]].id, d[V[nw]].w);
m--;
} else {
vis[rc] = 1;
while(nw) {
printf("%d %d %d %d\n", d[V[nw]].id, d[V[nw]].w, d[rc].id, k - d[V[nw]].w);
--m;
vis[V[nw]] = 1;
nw = bck[nw];
}
}
solve();
return ;
}
int main() {
// freopen("dish.in", "r", stdin);
// freopen("dish.out", "w", stdout);
scanf("%d", &T);
while(T-- > 0) {
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; ++i) {
scanf("%d", &d[i].w);
d[i].id = i;
}
init();
if(m >= n - 1)
solve();
else
solve2();
}
return 0;
}
```