codeforces 1809C

很巧妙的构造
题目链接

题目大意

要求构造长度为$n$的数组满足以下条件

• 任意$i$，$-1000<=a[i]<=1000$
• 有$k$个和为正数的子串
• 其余子串和为负数

思路

我们发现与子数组内元素的和有关，所以想到前缀和。
要求和是正的，所以我们想，在左右端点为$i,j$的前缀和串中，怎么表示和是正数？
$i<j,pre[j]-pre[i]>0$
而现在我们需要$k$个正子串，即找到$k$对合法的正序对$i,j$
我们想到冒泡排序，每次是将一个逆序对反转成正序对，那就先构造一个长为$n+1$的逆序数组，再用冒泡处理就行了

ACcode

#include<bits/stdc++.h>using namespace std;#define int long longvoid solve()
{int n,k;cin>>n>>k;vector<int>a(n+3);for(int i=0;i<=n;i++)a[i]=n-i+1;for(int i=0;i<=n;i++){for(int j=i+1;j<=n;j++){if(k>0){k--;swap(a[i],a[j]);}}}for(int i=1;i<=n;i++)cout<<a[i]-a[i-1]<<' ';cout<<'\n';
}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}