Educational Codeforces Round 95 (Rated for Div. 2) B. Negative Prefixes (贪心,构造)

题意:给你一串长度为\(n\)的序列,有的位置被锁上了,你可以对没锁的位置上的元素任意排序,使得最后一个\(\le0\)的前缀和的位置最小,求重新排序后的序列.
题解:贪心,将所有能动的位置从大到小排个序就行了.

代码:

struct misaka{

	int a;

	int loc;

}e[N];

int t;

int n;

int main() {

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

	t=read();

	while(t--){

		n=read();

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

			e[i].a=read();

		}

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

			e[i].loc=read();

		}

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

			for(int j=0;j<n;++j){

				if(e[i].loc!=1 && e[j].loc!=1){

					if(e[j].a<e[i].a) swap(e[i],e[j]);

				}

			}

		}

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

			printf("%d ",e[i].a);

		}

		puts("");

	}

    return 0;

}

巴特西

Educational Codeforces Round 95 (Rated for Div. 2) B. Negative Prefixes (贪心,构造)

最新文章

热门文章