链接: https://codeforces.com/contest/1244/problem/G
题意: 给出 2 个序列 p,q 长度为 n, 元素都是 1,2 ,3....n, 给出 k, 求 尽可能大 sigma(max(pi, qi)) 且小于 k 的时候如何安排序列的元素, 若无法满足条件,-1
题解: 贪心, 最小的情况两个序列都是 1,2,3,4...n, 最大的情况一个序列顺序一个序列倒序, 求和和 k 比较可判断是否有解,
要求尽可能大的, 我们不断的 a[i] 和 a[n-i+1] 进行交换, 这样交换产生的贡献是递减的并且连续的, 若在 x 处交换后超过了 k, 我们一定可以右边向走左找到最优解.
- #include <bits/stdc++.h>
- #define IO_read iOS::sync_with_stdio(false);cin.tie(0)
- #define fre freopen("in.txt", "r", stdin)
- #define _for(i,a,b) for(int i=a; i<b; i++)
- #define _rep(i,a,b) for(int i=a; i<=b; i++)
- #define inf 0x3f3f3f3f
- #define lowbit(a) ((a)&-(a))
- using namespace std;
- typedef long long ll;
- template <class T>
- void read(T &x)
- {
- char c; bool op=0;
- while(c=getchar(), c<'0'||c>'9') if(c=='-') op=1;
- x=c-'0';
- while(c=getchar(), c>='0'&&c<='9') x=x*10+c-'0';
- if(op) x=-x;
- }
- template <class T>
- void write(T x)
- {
- if(x<0) putchar('-'), x=-x;
- if(x>=10) write(x/10);
- putchar('0'+x%10);
- }
- const int maxn=1e6+5;
- int a[maxn], b[maxn];
- ll n, k, ans, max_ans;
- int main()
- {
- IO_read;
- //fre;
- cin>>n>>k;
- if(k<n*(n+1)/2){
- cout<<-1<<"\n"; return 0;
- }
- max_ans= n&1? ((n+1)/2+n)*(n+1)/2-(n+1)/2:(n+(n+2)/2)*n/2;
- if(k>=max_ans){
- cout<<max_ans<<"\n";
- for(int i=1; i<=n; i++) cout<<i<<"\n"[i==n];
- for(int i=n; i>=1; i--) cout<<i<<"\n"[i==1];
- return 0;
- }
- ans=n*(n+1)/2;
- for(int i=1; i<=n; i++) a[i]=b[i]=i;
- for(int i=1; i<=n/2; i++)
- {
- int val=a[n-i+1]-a[i];
- if(ans+val>k){
- int j=i+k-ans;
- ans=ans+a[j]-a[i];
- swap(a[i], a[j]);
- break;
- }
- ans+=val; swap(a[i], a[n-i+1]);
- }
- cout<<ans<<"\n";
- for(int i=1; i<=n; i++) cout<<a[i]<<"\n"[i==n];
- for(int i=1; i<=n; i++) cout<<b[i]<<"\n"[i==n];
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3263983.html