codeforces Div.2 899C Dividing the numbers

xiaoxiao2021-02-28  10

大意: 划分1-n的集合,将其分为两个,要求两个集合的和之差最小。 求集合(任意输出)

思路: 容易想到,首位配对的方法去取出来,差值必为0或1(差值为绝对值) 难点在选取。 现在知道差值为0或1 按照奇偶分为两个集合 从后往前检查,如果差值不为0或1 那么讲两个数字交换,交换后必然导致差值-2 当差值为0或1的时候,停止交换,即为答案。

实现代码:

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int,int> pii; #define mem(s,t) memset(s,t,sizeof(s)) #define D(v) cout<<#v<<" "<<v<<endl #define inf 0x3f3f3f3f #define pb push_back //#define LOCAL const int mod=1e9+7; const int MAXN =1e5+10; int main() { int n; cin>>n; vector<int> a,b; ll suma=0,sumb=0; for(int i=1;i<=n;i++){ if(i&1) a.pb(i),suma+=i; else b.pb(i),sumb+=i; } ll ret=abs(sumb-suma); for(int i=a.size()-1,j=b.size()-1;i>=0&&j>=0;i--,j--){ swap(a[i],b[j]); ret-=2; if(abs(ret)<=1) break; } cout<<abs(ret)<<endl; cout<<a.size(); for(int i=0;i<a.size();i++){ cout<<" "<<a[i]; } cout<<endl; return 0; }
转载请注明原文地址: https://www.6miu.com/read-2000252.html

最新回复(0)