题解 P6726 【[COCI2015-2016#5] POPLAVA】

JK_LOVER · 2020-08-04 20:39:46 · 题解

题意

使得柱状图的容量为 X 。如果不存在，则输出 -1。否则输出任意一种方案。QAQ 。

分析

众所周知构造永远要比解决难度大，考虑这个题的特殊性

• 最左和最右的的柱子永远没法储水。

• 储水的柱子左右总有比它高的。

那么我们如果画这样一张图就一目了然了。

这样所有储水的柱子全在 n 号和 n-1 号柱子之间了。移除一个柱子的那么储水就会减少 (n-1)-id 这样多。那么我们只要将标号有小到大枚举，这样就保证了不重不漏。而无解的情况就只有

划重点：不要用 dfs 实现这样过程，会很慢。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1000100;
LL n,X,maxflow,d;
int ans = 0,top = 0,cnt[N],vis[N];
void dfs(LL f)
{
    if(ans) return;
    if(f == 0){
//      sort(cnt+1,cnt+1+top);
        for(int i = 1;i <= top;i++){
            printf("%d ",cnt[i]);
        }
        printf("%d ",n);
        for(int i = 1;i <= n-2;i++)
        if(!vis[i]) printf("%d ",i);
        printf("%d ",n-1);
        ans = 1;
        exit(0);
    }
    for(int i = 1;i <= n-2;i++)
    {
        if(!vis[i] && (f - ((n-1) - i) >= 0))
        {
            cnt[++top] = i;vis[i] = 1;
            dfs(f - ((n-1)-i));
        }
    }
}
int main()
{
    cin>>n>>X;
    maxflow = (n-1)*(n-2) - (1+(n-2))*(n-2)/2;
    d = maxflow - X;
    if(d < 0){
        printf("-1\n");
        return 0;
    }
    dfs(d);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1000100;
LL n,X,maxflow,d;
int ans = 0,top = 0,cnt[N],vis[N];
int main()
{
    cin>>n>>X;
    maxflow = (n-1)*(n-2) - (1+(n-2))*(n-2)/2;
    d = maxflow - X;
    if(d < 0){
        printf("-1\n");
        return 0;
    }
    for(int i = 1;i <= n-2;i++)
    {
        if(d - ((n-1)-i) >= 0)
        {
            vis[i] = 1;
            cnt[++top] = i;
            d -= ((n-1)-i);
        }
    }
//  sort(cnt+1,cnt+1+top);
    for(int i = 1;i <= top;i++){
        printf("%d ",cnt[i]);
    }
    printf("%d ",n);
    for(int i = 1;i <= n-2;i++)
    if(!vis[i]) printf("%d ",i);
    printf("%d ",n-1);
    return 0;
}