A. Life of a Flower

题目描述

彼佳有一朵有趣的花。彼佳是个大忙人，所以有时会忘记浇水。从彼佳的生命开始，你有 n 天的时间，你必须确定他的花最终发生了什么。

花长成如下：

如果花连续两天不浇水，它就会死。
如果花在第 i 天浇水，它会生长 1 厘米。
如果花在第 i 天和第 (i−1) 天 (i>1) 浇水，那么它会生长 5 厘米而不是 1 厘米。
如果花在第 i 天没有浇水，它就不会生长。
在第一天开始时，花高 1 厘米。 n 天后它的高度是多少？

输入

每个测试包含多个测试用例。第一行包含测试用例数 t ( 1 ≤ t ≤ 100 ) t (1≤t≤100) t(1≤t≤100)。测试用例的描述如下。

每个测试用例的第一行包含唯一的整数 n ( 1 ≤ n ≤ 100 ) n (1≤n≤100) n(1≤n≤100)。

每个测试用例的第二行包含 n 个整数 a 1 , a 2 , … , a n （ a i = 0 或 a i = 1 ） a_1,a_2,…,a_n（a_i=0 或 a_i=1） a1​,a2​,…,an​（ai​=0或ai​=1）。如果 a i = 1 a_i=1 ai​=1，花在第i天浇水，否则不浇水。

输出

对于每个测试用例，打印一个整数 k k k—— n n n 天后花的高度，或者 -1，如果花死了。

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 110;
int a[maxn];
void solve(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int len = 1 + a[1];
    for (int i = 2; i <= n; i++){
        if (a[i] + a[i - 1] == 0){
            len = -1;
            break;
        }
        if (a[i] == 1 && a[i - 1] == 1)
            len += 5;
        else if (a[i] == 1)
            len++;
    }
    cout << len << "\n";
}

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

B. Array Eversion

题目描述

给定一个长度为 n n n 的数组 a a a。

让我们定义翻转操作。令 x = a n x=a_n x=an​。然后数组 a a a 被划分为两部分：左部分和右部分。左侧部分包含不大于 x ( ≤ x ) x (≤x) x(≤x) 的 a a a 元素。右侧部分包含严格大于 4 x ( > x ) 4x (>x) 4x(>x) 的 a a a 元素。每个部分中元素的顺序保持与操作前相同，即。 e.分区稳定。然后将数组替换为左右部分的串联。

例如，如果数组 a a a 是 [2,4,1,5,3]，则反转是这样的：[2,4,1,5,3]→[2,1,3],[4,5]→[2,1,3,4,5]。

我们从数组 a a a 开始并在这个数组上执行翻转。我们可以证明，经过几次外翻后，数组 a a a 停止变化。输出最小数 k k k 使得数组在 k k k 次翻转后停止变化。

输入

每个测试包含多个测试用例。第一行包含测试用例数 t ( 1 ≤ t ≤ 100 ) t (1≤t≤100) t(1≤t≤100)。测试用例的描述如下。

第一行包含一个整数 n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) n (1≤n≤2⋅10^5) n(1≤n≤2⋅105)。

第二行包含 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。

输出

对于每个测试用例，打印一个整数 k k k - 数组停止更改后的翻转次数。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn=2e5+5;
int n, x, mx;
int a[maxn];
int ans[maxn];
int len;
void solve(){
    cin >> n;
		mx = 1;
		len = 0;
		for(int i = 1; i <= n; i++){
			cin >> a[i];
			if(a[mx] <= a[i])
				mx = i;
		}
		ans[++len] = a[mx];
		for(int i = mx + 1; i <= n; i++){
			while(ans[len] <= a[i])
				len--;
			ans[++len] = a[i];
		}
		cout << len - 1 << endl;
}

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

C. Minimize Distance

题目描述

共有 n n n 个仓库位于数轴上。对于 1 ≤ i ≤ n 1≤i≤n 1≤i≤n，站点 i i i 位于 x i x_i xi​ 点。

你是一个有 n n n 袋货物的推销员，试图向 n n n 个仓库中的每个仓库运送一袋货物。您和 n n n 个行李最初位于原点 0 0 0。您一次最多可以携带 k k k 个行李。您必须从原产地收集所需数量的货物，将它们运送到相应的仓库，然后返回原产地提取您的下一批货物。

计算将所有货物袋运送到仓库所需的最小距离。送完所有行李后，您无需返回原点。

输入

每个测试包含多个测试用例。第一行包含测试用例数 t ( 1 ≤ t ≤ 10500 ) t (1≤t≤10500) t(1≤t≤10500)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 n n n 和 k ( 1 ≤ k ≤ n ≤ 2 ⋅ 1 0 5 ) k (1≤k≤n≤2⋅10^5) k(1≤k≤n≤2⋅105)。

每个测试用例的第二行包含 n n n 个整数 x 1 , x 2 , … , x n ( − 1 0 9 ≤ x i ≤ 1 0 9 ) x_1,x_2,…,x_n (−10^9≤x_i≤10^9) x1​,x2​,…,xn​(−109≤xi​≤109)。一些仓库可能共享相同的位置。

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

输出

对于每个测试用例，输出一个整数，表示将所有货物袋子运送到仓库所需的最小距离。

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
void solve(){
    ll n, m;
    cin >> n >> m;
    vector<ll> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    sort(v.begin(), v.end());
    ll ans = 0;
    for (int i = n - 1; i >= 0 && v[i] >= 0; i -= m)
        ans += v[i];
    for (int i = 0; i < n && v[i] < 0; i += m)
        ans += abs(v[i]);
    cout << 2 * ans - max(abs(v[0]), abs(v[n - 1])) << endl;
}

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