C

//今天仔细看数据范围了，肯定是dp，但是没贪对方向
//只关注到了性质1：由于只看相邻那只需要维护两个数组看他们的末尾就可以
//性质2：这个维护要按照什么规则，我的贪心的是短视，题解则是给出了严谨的思路
//1x<a,x>b,直接a=b，反正都要惩罚，选个区间高的,a<x<b:此时贪心的把数据填到b，
//稍微证明一下：对于a=2，b=6；x1=3，x2=4；(写具体数字是为了直观看到大小)
//先a后a乘法2（4，6），先a后b惩罚1（3，4），先b后b乘法1（2，4）；
//后续一旦有x<a,x>b将重置性质（后者会有代价），但是假设一直都是a<x<b；那么前者要么乘法要么重置
//...最后全a=全b+1或b
#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> ori(n);
    for(int i = 0; i < n; i++) {
        cin >> ori[i];
    }

    int t1 = ori[0];
    int t2 = INT32_MAX;
    int cnt = 0;

    for(int i = 1; i < n; i++){
        int ai = ori[i];
        if(t1>t2){
            swap(t1,t2);
        }
        if(ai <= t1){
            t1 = ai;
        }
        else if(ai <= t2){
            t2 = ai;
        }
        else{
            t1 = ai;
            cnt++;
        }
    }

    cout << cnt << "\n";
}

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

C

//由数据范围和状态不难设计dpnk
//状态转移太牛了，利用滑动窗口的性质保证每一种可能都被枚举
//集合划分，不选就是继承 dp[i - 1][j] + arr[i]
//选的话，要选往前连续1到（k-j）个
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
    int n, k;
    cin >> n >> k;
    vector<ll> arr(n + 1);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    vector<vector<ll>> dp(n + 1, vector<ll>(k + 1,0));
    vector<vector<ll>> v(n + 1, vector<ll>(k + 1,0));
    if(n==1){
        cout<<arr[1]<<"\n";
        return;
    }
    for (int i = 1; i <= n; i++) {
        ll mmin = arr[i];
        v[i][0]=arr[i];
        for (int j = i-1; j >= 1 && i - j <= k; j--) {
            mmin = min(mmin, arr[j]);
            v[i][i - j] = mmin;
        }

    }

    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = dp[i - 1][j] + arr[i];
            for (int d = 1; d<=j && i - d >= 1; d++) {
              dp[i][j] = min(dp[i][j], dp[i - d -1][j - d] + v[i][d] * (d+1));
            }
        }
    }

   cout<<dp[n][k]<<"\n";

}

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

B

//乱搞，莫名奇妙搞对了
//看题解前，先说说思路
//当k>=n时候可以无限填充，也就是说，直接取最大的作为标
//当k<n时候，由于买车必须不同，所以一群短的可以和一个长的拼凑此时对于那部分小的可以利用
//同除定理的思想（均匀）涂在k-1个位置上，如果有余数就多一层。但是考虑到难以把这部分高的
//剔除出来，并且高的不可以折断，于是我们直接把最大的那个加进去一起均匀分配，并且假设这一种
//最优的方法是正确的也就是不折叠最高的，那么这个贪心的答案正确的前提是均匀涂抹后>=
//最高的，这样子才不会折叠，假设折叠了，直接输出最高的高度就好
//题解的证明：
//1由于买车必须不同，所以候选ans必须包含max（arr【i】）
//2所需最少客服是sum/k向上取整
//确实...好简洁明了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
    int n,k;
    cin>>n>>k;
    ll arr[n+1];
    ll ss=0;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        ss+=arr[i];
    }
    sort(arr+1,arr+1+n);
    if(k>=n){
        cout<<arr[n]<<"\n";
    }else{
        if(ss/k>=arr[n])cout<<(ss/k+ll(ss%k>0))<<" \n";
        else cout<<arr[n]<<"\n";
    }

}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }

}

///涨知识了区间覆盖次数问题可以用差分
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int t;
const int N = 200010;
int n, m, k;
vector<long long> st, a;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    while (t--) {
        cin >> n >> m >> k;

        st.clear();
        st.reserve(n * m);

        vector<vector<int>> vc(n + 1, vector<int>(m + 1, 0));

        for (int i = 1; i <= n - k + 1; i++) {
            for (int j = 1; j <= m - k + 1; j++) {
                vc[i][j]++;
                if (i + k <= n) vc[i + k][j]--;
                if (j + k <= m) vc[i][j + k]--;
                if (i + k <= n && j + k <= m) vc[i + k][j + k]++;
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i > 1) vc[i][j] += vc[i - 1][j];
                if (j > 1) vc[i][j] += vc[i][j - 1];
                if (i > 1 && j > 1) vc[i][j] -= vc[i - 1][j - 1];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                st.push_back(vc[i][j]);
            }
        }

        sort(st.begin(), st.end(), greater<long long>());

        int w;
        cin >> w;
        a.resize(w);
        for (int i = 0; i < w; i++) {
            cin >> a[i];
        }

        sort(a.begin(), a.end(), greater<long long>());

        long long ans = 0;
        for (int i = 0; i < w; i++) {
            ans += a[i] * st[i];
        }

        cout << ans << '\n';
    }

    return 0;
}

//