2021-12-28

文章目录

A. Construct a Rectangle

题目大意：

有三个长度为 l1、l2 和 l3 的整数棒。

你被要求将它们中的一个准确地分成两部分，这样：

两个部分都具有正（严格大于 0）整数长度；
碎片的总长度等于木棒的原始长度；
可以从生成的四根木棍构建一个矩形，这样每根木棍都可以用作它的一侧。
正方形也被认为是矩形。

确定是否可以这样做。

输入
第一行包含一个整数 t ( 1 ≤ t ≤ 1 0 4 ) t (1≤t≤10^4) t(1≤t≤104)——测试用例的数量。

每个测试用例的唯一一行包含三个整数 l 1 , l 2 , l 3 ( 1 ≤ l i ≤ 1 0 8 ) l_1,l_2,l_3 (1≤l_i≤10^8) l1​,l2​,l3​(1≤li​≤108)——木棒的长度。

输出
对于每个测试用例，如果可以将一根棍子分成两块，长度为正整数，从而可以从生成的四根棍子中构造一个矩形，则打印“YES”。否则，打印“NO”。

您可以在任何情况下打印每个字母（例如，字符串 yEs、yes、Yes 和 YES 都被识别为肯定答案）。

测试样例：

input
4
6 1 5
2 5 2
2 4 2
5 5 4
output
YES
NO
YES
YES

【code】:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
void solve(){
   
    int a[3] = {
   0};
    for (int i = 0; i < 3;i++){
   
        cin >> a[i];
    }
    sort(a, a + 3);
    if((a[0]+a[1])==a[2]){
   
        cout << "yes\n";
    }else if(a[0]==a[1]&&a[2]%2==0){
   
        cout << "yes\n";
    }else if(a[1]==a[2]&&a[0]%2==0){
   
        cout << "yes\n";
    }else
        cout << "NO\n";
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

B. Berland Music

题目大意：

Berland Music 是一种音乐流媒体服务，专为支持 Berland 本地艺术家而构建。它的开发人员目前正在开发歌曲推荐模块。

所以想象一下 Monocarp 得到了推荐的 n n n 首歌曲，编号从 1 1 1 到 n n n。第 i i i 首歌曲的预测评分等于 p i p_i pi​，其中 1 ≤ p i ≤ n 1≤p_i≤n 1≤pi​≤n 并且从 1 1 1 到 n n n 的每个整数都只出现一次。换句话说， p p p 是一个排列。

听完他们每个人的声音后，莫诺卡普按下了喜欢或不喜欢的按钮。让他的投票序列用字符串 s s s 表示，这样 s i s_i si​=0 表示他不喜欢第 i 首歌曲，而 s i s_i si​=1 表示他喜欢它。

现在，该服务必须以如下方式重新评估歌曲评分：

新的评分 q 1 , q 2 , … , q n q_1,q_2,…,q_n q1​,q2​,…,qn​ 仍然形成排列（ 1 ≤ q i ≤ n 1≤q_i≤n 1≤qi​≤n；从 1 到 n 的每个整数只出现一次）；
Monocarp 喜欢的每首歌曲的评分都应该高于 Monocarp 不喜欢的每首歌曲的评分（正式地，对于所有 i,j 使得 s i s_i si​=1 和 s j s_j sj​=0， q i > q j q_i>q_j qi​>qj​ 应该成立）。
在所有有效排列 q q q 中，找到具有最小值 ∑ i = 1 n ∣ p i − q i ∣ ∑_{i=1}^{n}|p_i−q_i| ∑i=1n​∣pi​−qi​∣ 的排列，其中 ∣ x ∣ |x| ∣x∣是 x x x 的绝对值。

打印排列 q 1 , q 2 , . . . , q n q_1,q_2,...,q_n q1​,q2​,...,qn​。如果有多个答案，您可以打印其中任何一个。

输入
第一行包含一个整数 t ( 1 ≤ t ≤ 1 0 4 ) t (1≤t≤10^4) t(1≤t≤104)——测试用例的数量。

每个测试用例的第一行包含一个整数 n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) n (1≤n≤2⋅10^5) n(1≤n≤2⋅105)——歌曲的数量。

每个测试用例的第二行包含 n n n 个整数 p 1 , p 2 , … , p n ( 1 ≤ p i ≤ n ) p_1,p_2,…,p_n (1≤p_i≤n) p1​,p2​,…,pn​(1≤pi​≤n)——预测评分的排列。

第三行包含单个字符串 s s s，由 n n n 个字符组成。每个字符都是 0 或 1。0 表示 Monocarp 不喜欢这首歌，1 表示他喜欢这首歌。

所有测试用例的 n n n 总和不超过 2 ⋅ 1 0 5 2⋅10^5 2⋅105。

输出
对于每个测试用例，打印一个排列 q q q——重新评估的歌曲评分。如果有多个答案使得 ∑ i = 1 n ∣ p i − q i ∣ ∑_{i=1}^{n}|p_i−q_i| ∑i=1n​∣pi​−qi​∣尽可能少，您可以打印其中任何一个。

测试样例：

input
3
2
1 2
10
3
3 1 2
111
8
2 3 1 8 5 4 7 6
01110001
output
2 1
3 1 2
1 6 5 8 3 2 4 7

【code】:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
struct node{
   
    int data, vis, flag;
};
bool cmp(node a,node b){
   
    if(a.flag!=b.flag)
        return a.flag < b.flag;
    else
        return a.data < b.data;
}
void solve(){
   
    int n;
    cin >> n;
    vector<node> a(n+1);
    vector<int> b(n+1);
    for (int i = 1; i <= n;i++){
   
        cin >> a[i].data;
        a[i].vis = i;
    }
    string s;
    cin >> s;
    for (int i = 0; i < s.size();i++){
   
        if(s[i]=='1'){
   
            a[i+1].flag = 1;
        }
    }
    sort(a.begin(), a.end(), cmp);
    for (int i = n ; i > 0;i--){
   
        b[a[i].vis] = i;
    }
    for (int i = 1;i<=n;i++){
   
        cout << b[i] << " ";
    }
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

C. Set or Decrease

题目大意：

给定一个整数数组 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​ 和整数 k k k。

一步就可以

要么选择某个索引 i i i 并将 a i ai ai 减一（使 a i = a i − 1 a_i=a_i−1 ai​=ai​−1）；
或者选择两个索引 i i i 和 j j j 并设置 a i a_i ai​ 等于 a j a_j aj​（使 a i = a j a_i=a_j ai​=aj​）。
使数组 ∑ i = 1 a i ≤ k \sum_{i=1}a_i≤k ∑i=1​ai​≤k 的总和所需的最少步数是多少？ （您可以将数组的值设为负数）。

输入
第一行包含一个整数 t ( 1 ≤ t ≤ 1 0 4 ) t (1≤t≤10^4) t(1≤t≤104)——测试用例的数量。

每个测试用例的第一行包含两个整数 n n n 和 k k k ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ; 1 ≤ k ≤ 1 0 15 ) (1≤n≤2⋅10^5; 1≤k≤10^{15}) (1≤n≤2⋅105;1≤k≤1015)——数组 a a a 的大小及其总和的上限。

每个测试用例的第二行包含 n n n 个整数 a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 1 0 9 ) a_1,a_2,…,a_n (1≤a_i≤10^9) a1​,a2​,…,an​(1≤ai​≤109)——数组本身。

保证所有测试用例的 n n n 总和不超过 2 ⋅ 1 0 5 2⋅10^5 2⋅105。

输出
对于每个测试用例，打印一个整数——使 ∑ i = 1 a i ≤ k \sum_{i=1}a_i≤k ∑i=1​ai​≤k 的最小步骤数。

测试样例：

input
4
1 10
20
2 69
6 9
7 8
1 2 1 3 1 2 1
10 1
1 2 3 1 2 6 1 6 8 10
output
10
0
2
7

【code】:



#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int inf=0x3f3f3f3f;
const int maxn=2e5+5;
void solve(){
   
    int n;
    ll k;
    cin >> n >> k;
    int a[maxn] = {
   0};
    for (int i = 1; i <= n;i++){
   
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    ll s = 0, S = 0;
    for (int i = 1;i<=n;i++){
   
        S += a[i];
    }
    ll ans = max(0LL, S - k);
    for (int i = n; i >= 2;i--){
   
        s += a[i];
        ll x = (k - (S - s - a[1])) / (n - i + 2);
        while((S-a[1]-s+x+(n-i+1)*x>k))
            --x;
        ans = min(ans, n - i + 1 + max(a[1] - x, 0LL));
    }
    cout << ans << endl;
}

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}