Codeforces Round #673 (Div. 2) B. Two Arrays (贪心)

题意:给你一组数\(a\)和一个数\(T\),将这组数分为两组\(c\)和\(d\),定义\(f(x)\)为数组\(x\)中任意两个不同元素的和为\(T\)的个数,问为了使\(min(f(c)+f(d))\),应该怎样对\(a\)分组.
题解:我们可以分成三种情况,假如一组数中所有元素都\(< \frac{T}{2}\),或者\(>\frac{T}{2}\),那么它们的\(f(x)\)都为\(0\),然而对于\(a[i]=\frac {T}{2}\)的情况,我们将其交叉放在两组即可.

代码:

int t;

int n;

ll T;

ll a[N];

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>t;

    while(t--){

    	cin>>n>>T;

    	for(int i=1;i<=n;++i){

    		cin>>a[i];

    	}

    	int col;

    	int cnt=0;

    	for(int i=1;i<=n;++i){

    		if(T%2==0 && a[i]*2==T){

    			cnt=1-cnt;

    			col=cnt;

    		}

    		else if(a[i]<=T/2){

    			col=0;

    		}

    		else col=1;

    		cout<<col<<" ";

    	}

    	cout<<'\n';

    }

    return 0;

}

巴特西

Codeforces Round #673 (Div. 2) B. Two Arrays (贪心)

最新文章

热门文章