Codeforces Round #723 (Div. 2)
A. Mean Inequality
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an array aa of 2n2n distinct integers. You want to arrange the elements of the array in a circle such that no element is equal to the the arithmetic mean of its 22 neighbours.
More formally, find an array bb, such that:
bb is a permutation of aa.
For every ii from 11 to 2n2n, bi≠bi−1+bi+12bi≠bi−1+bi+12, where b0=b2nb0=b2n and b2n+1=b1b2n+1=b1.
It can be proved that under the constraints of this problem, such array bb always exists.
Input
The first line of input contains a single integer tt (1≤t≤1000)(1≤t≤1000) — the number of testcases. The description of testcases follows.
The first line of each testcase contains a single integer nn (1≤n≤25)(1≤n≤25).
The second line of each testcase contains 2n2n integers a1,a2,…,a2na1,a2,…,a2n (1≤ai≤109)(1≤ai≤109) — elements of the array.
Note that there is no limit to the sum of nn over all testcases.
Output
For each testcase, you should output 2n2n integers, b1,b2,…b2nb1,b2,…b2n, for which the conditions from the statement are satisfied.
Example
input
Copy
3 3 1 2 3 4 5 6 2 123 456 789 10 1 6 9
output
Copy
3 1 4 2 5 6 123 10 456 789 9 6
Note
In the first testcase, array [3,1,4,2,5,6][3,1,4,2,5,6] works, as it's a permutation of [1,2,3,4,5,6][1,2,3,4,5,6], and 3+4/2≠1 3+4/2≠1, 1+2/2≠4 1+2/2≠4, 4+5/2≠2 4+5/2≠2, 2+6/2≠5 2+6/2≠5, 5+3/2≠6 5+3/2≠6, 6+1/2≠3 6+1/2≠3.
题意
前一个加后一个不等于中间一个
所以可以先排序
然后再输出小大小大交替输出
上代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[50];
for(int i=0;i<n*2;i++)
cin>>a[i];
sort(a,a+n*2);
for(int i=0;i<n;i++)
{
cout<<a[i]<<" "<<a[2*n-i-1]<<" ";
}
cout<<endl;
}
}
B. I Hate 1111
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an integer xx. Can you make xx by summing up some number of 11,111,1111,11111,…11,111,1111,11111,…? (You can use any number among them any number of times).
For instance,
- 33=11+11+1133=11+11+11
- 144=111+11+11+11144=111+11+11+11
Input
The first line of input contains a single integer tt (1≤t≤10000)(1≤t≤10000) — the number of testcases.
The first and only line of each testcase contains a single integer xx (1≤x≤109)(1≤x≤109) — the number you have to make.
Output
For each testcase, you should output a single string. If you can make xx, output "YES" (without quotes). Otherwise, output "NO".
You can print each letter of "YES" and "NO" in any case (upper or lower).
Example
input
Copy
3 33 144 69
output
Copy
YES YES NO
Note
Ways to make 3333 and 144144 were presented in the statement. It can be proved that we can't present 6969 this way.
这题只要11和111就可以组成所有的由1组成的数
所以只要算多少个11和111就行，
例如1111=11*100+11
11111=111*100+11
能组成就是Yes不能就是No
代码
#include<iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int k=n%11;
n=n-k*111;
if(n>=0)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}C1. Potions (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
This is the easy version of the problem. The only difference is that in this version n≤2000n≤2000. You can make hacks only if both versions of the problem are solved.
There are nn potions in a line, with potion 11 on the far left and potion nn on the far right. Each potion will increase your health by aiai when drunk. aiai can be negative, meaning that potion will decrease will health.
You start with 00 health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.
What is the largest number of potions you can drink?
Input
The first line contains a single integer nn (1≤n≤20001≤n≤2000) — the number of potions.
The next line contains nn integers a1a1, a2a2, ... ,anan (−109≤ai≤109−109≤ai≤109) which represent the change in health after drinking that potion.
Output
Output a single integer, the maximum number of potions you can drink without your health becoming negative.
Example
input
Copy
6 4 -4 1 -3 1 -3
output
Copy
5
Note
For the sample, you can drink 55 potions by taking potions 11, 33, 44, 55 and 66. It is not possible to drink all 66 potions because your health will go negative at some point
这题没想出来
dalao告诉我是反贪心
用先序序列就可以做
看完代码后觉得dalao太厉害了
佩服
我来说一下主要思想实现
一瓶瓶药嗑下去，当身体吃不消的时候就吐出来对身体伤害最大的药，
吐完后接着嗑药
直到最后一瓶药为止
上代码
#include<bits/stdc++.h>
using namespace std;
long long c=0;
long long ans=0;
long long n;
priority_queue<long long,vector<long long>,greater<long long> >pq;
int main(){
cin>>n;
while(n--){
long long x;cin>>x;
pq.push(x),c+=x,ans++;
if(c<0)c-=pq.top(),pq.pop(),ans--;
}
cout<<ans;
}
C2. Potions (Hard Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
This is the easy version of the problem. The only difference is that in this version n≤2000n≤2000. You can make hacks only if both versions of the problem are solved.
There are nn potions in a line, with potion 11 on the far left and potion nn on the far right. Each potion will increase your health by aiai when drunk. aiai can be negative, meaning that potion will decrease will health.
You start with 00 health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.
What is the largest number of potions you can drink?
Input
The first line contains a single integer nn (1≤n≤200000 1≤n≤200000) — the number of potions.
The next line contains nn integers a1a1, a2a2, ... ,anan (−109≤ai≤109−109≤ai≤109) which represent the change in health after drinking that potion.
Output
Output a single integer, the maximum number of potions you can drink without your health becoming negative.
Example
input
Copy
6 4 -4 1 -3 1 -3
output
Copy
5
Note
For the sample, you can drink 55 potions by taking potions 11, 33, 44, 55 and 66. It is not possible to drink all 66 potions because your health will go negative at some point
进阶版就是数据范围变大了
用先序序列完全可以过
代码都不用改