Codeforces Round ＃807 (Div 2.) AB

A

 

A. 标记摄影师

每次测试的时间限制

1 秒

每次测试的内存限制

为 256 MB

输入

标准输入

输出

标准输出

马克被要求合影2n2n人。这我我-人身高h我hi单位。

为此，他命令这些人分成两排，前排和后排，每排由nn人。但是，为了确保正确看待每个人，jj-后排的第 个人必须至少xx单位高于jj-每人前排的第 0 个人jj之间11和nn包容。

帮助标记确定这是否可能。

输入

第一行包含一个整数tt (1≤吨≤1001≤吨≤100） — 测试用例的数量。每个测试用例由两行组成。

每个测试用例的第一行包含两个正整数nn和xx (1≤n≤1001≤n≤100,1≤x≤1031≤x≤103） — 每行中的人数和 Mark 想要的最小差异。

每个测试用例的第二行包含2n2n正整数h1,h2，...，h2nh1，h2，...，h2n (1≤h我≤1031≤小时i≤103） — 每个人的身高（单位）。

请注意，总和nn在所有测试用例中都是无限制的。

输出

对于每个测试用例，如果 Mark 可以安排满足其条件的人，请打印一行包含“YES”，否则打印“NO”。

您可以在任何情况下打印每个字母（例如，是，是，是的，是的，yE都将被识别为肯定的答案）。

例

输入

复制

3 3 6 1 3 9 10 12 16 3 1 2 5 2 2 2 5 1 2 8 6 

输出

复制

YES NO YES 

注意

在第一个测试用例中，一个可能的顺序是将第三、第五和第六人放在后排，第二、第一和第四人放在前排。人们的高度会是这样的。

返回	99	1212	1616
前面	33	11	1010

它的工作原理是因为

• h3−h2=9−3≥6h3−h2=9−3≥6,
• h5−h1=12−1≥6h5−h1=12−1≥6和
• h6−h4=16−10≥6h6−h4=16−10≥6.

在第二个测试用例中，可以证明没有办法以满足条件的方式对人员进行排序。

在第三个测试用例中，安排人们满足条件的唯一方法是让第一个人在后排，第二个人在前排。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int _;
	cin>>_;
	int a[1001],b[1001],c[1001];
	while(_--){
		bool ok = true;
		int n,x;
		cin>>n>>x;
		for(int i = 1;i<=2*n;i++) cin>>a[i];
		sort(a+1,a+1+2*n);
		for(int i = 1;i<=n;i++){
			b[i]=a[i];
		}
		int j = 1;
		for(int i = n+1;i<=2*n;i++){
			c[j]=a[i];
			j++;
		}	
		for(int i = 1;i<=n;i++){
			if(c[i]-b[i]<x){
				ok = false;
			}
		}
		if(ok){
		cout<<"YES\n";		
	}else{
		cout<<"NO\n";
	}
	}
	
	return 0;
}

B

B. 标记扫尘器

每次测试的时间限制

为1.5秒

每次测试的内存限制

为 256 MB

输入

标准输入

输出

标准输出

马克正在打扫一排nn房间。这我我- 房间有一个非负尘位一个我ai.他有一台神奇的清洗机，可以做以下三步操作。

• 选择两个指数i<ji<j使得粉尘水平一个我ai,一个i+1i+1,......,一个j−1aj−1都严格大于00.
• 设置一个我ai自一个我−1ai−1.
• 设置一个jaj自一个j+1aj+1.

马克的目标是让一个1=一个2=...=一个n−1=0a1=a2=...=an−1=0这样他就可以很好地扫除nn- 房间。确定实现目标所需的最小操作数。

输入

第一行包含单个整数tt (1≤吨≤1041≤t≤104） — 测试用例的数量。

每个测试用例的第一行包含单个整数nn (2≤n≤2⋅1052≤n≤2⋅105） — 房间数。

每个测试用例的第二行包含nn整数一个1a1,一个2a2, ...,一个nan (0≤一个我≤1090≤ai≤109） — 每个房间的灰尘水平。

保证nn在所有测试用例中不超过2⋅1052⋅105.

输出

对于每个测试用例，打印一行包含单个整数 （ 最小操作数）。可以证明有一系列操作符合目标。

例

输入

复制

4 3 2 0 0 5 0 2 0 2 0 6 2 0 3 0 4 6 4 0 0 0 10 

输出

复制

3 5 11 0 

注意

在第一种情况下，一个可能的操作序列如下所示。

• 选择i=1i=1和j=2j=2，生成数组[1，1，0][1，1，0].
• 选择i=1i=1和j=3j=3，生成数组[0，1，1][0，1，1].
• 选择i=2i=2和j=3j=3，生成数组[0，0，2][0，0，2].

此时，一个1=一个2=0a1=a2=0，完成该过程。

在第二种情况下，一个可能的操作序列如下所示。

• 选择i=4i=4和j=5j=5，生成数组[0，2，0，1，1][0，2，0，1，1].
• 选择i=2i=2和j=3j=3，生成数组[0，1，1，1，1][0，1，1，1，1].
• 选择i=2i=2和j=5j=5，生成数组[0，0，1，1，2][0，0，1，1，2].
• 选择i=3i=3和j=5j=5，生成数组[0，0，0，1，3][0，0，0，1，3].
• 选择i=4i=4和j=5j=5，生成数组[0，0，0，0，4][0，0，0，0，4].

在最后一种情况下，数组已经满足条件。

 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void ok(){
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    ll ans = 0;
    int pos = 0;
    while(pos < n && a[pos] == 0)
        pos++;
    for(int i = pos; i < n-1; ++i){
        ans += a[i];
        if(a[i] == 0) ans++;
    }
    cout << ans << endl;
}
int main(){
    int t; cin >> t;
    while(t--) ok();
}