Problem - D - Codeforces

思路：

1. 只要数组同时存在正数与负数存在该排序存在
2. 因为存在正负数，所以对于任意一个值都小于max。
3. 那么我们可以排序后贪心每次都加一个小正数，直到不能再加就补一个大负数，然后就继续加正数，一直维持正数不超过即可

#include <bits/stdc++.h>
using namespace std;
#define ll     long long
#define int ll
int32_t main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t;cin>>t;while (t--){int n,x;cin>>n;vector<int>zh,fu;//他们没人放0，用于确认是否正负数都存在for (int i=1; i<=n; ++i){cin>>x;if (x>0)zh.push_back(x);else if (x<0)fu.push_back(x);}if (zh.empty()||fu.empty())//正负必须同时存在{cout<<"NO"<<endl;continue;}sort(zh.begin(),zh.end());sort(fu.begin(),fu.end());int i=0,j=0;int maxn=zh.back()-fu.front(),sum=0;vector<int>ans;while (i<(int)zh.size()&&j<(int)fu.size()){if (zh[i]+sum<maxn)//贪心加正数{ans.push_back(zh[i]);sum+=zh[i++];}else//不行补一个较大负数{ans.push_back(fu[j]);sum+=fu[j++];}}while (i<(int)zh.size())ans.push_back(zh[i++]);while (j<(int)fu.size())ans.push_back(fu[j++]);cout<<"YES"<<endl;while ((int)ans.size()<n)ans.push_back(0); //前面是没有存入0的，所以缺的话那就是0了for (auto &k:ans)cout<<k<<" ";cout<<endl;}return 0;
}

Problem - E - Codeforces

思路：

1. 设dp[i]表示i~n的连续拼接子串（无法连续拼接，设为-1）
2. maxn[i]表示在修改前可以取到的i~n区间的最多连续拼接子串数量，注意，不一定是到i~n连续，代表的是i或者i之后的dp[i]的最大值
3. f[i]表示修改后（当然你也可以不用修改啦）可以取到的i~n的连续拼接子串最大值（这个必须是i~n连续了）
4. 我们不难发现，答案只有0，1，2。
   1. 首先，如果a[i]=dp[i+1]（即i+1~n连续且子串数量为a[i])，理想情况，不用修改
   2. 修改1次时，我们可以着眼于是修改a[i]的值还是修改(i+1,n)这个区间
      1. 如果修改a[i],那么你首先需要保证(i+1,n)连续，即dp[i+1]!=-1。那么修改a[i]=f[i+1]即可
      2. 如果修改区间（此时区间一定不连续，不然我修改a[i]不就好了），那你只要满足a[i]<=f[i+1]，即修改后可以取到的最大f，那么可以一次操作结束（因为我们一部操作修改a[i+1]可以使得他跑到（i+1,n)任何一个位置，所以可以取值（1，f[i+1])
   3. 修改2次，不用说了

#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\\n"
#define int              long long
const int N = 3e5 + 10;
int dp[N];
int a[N],ans[N],maxn[N],f[N];
void mysolve()
{int n;cin>>n;for (int i=1; i<=n; ++i)cin>>a[i],dp[i]=-1,maxn[i]=f[i]=0;dp[n+1]=maxn[n+1]=f[n+1]=0;for (int i=n; i>=1; --i){if (i==n){if (a[i]==0)dp[i]=1;}else{if (dp[i+1]!=-1)//区间连续时{if (a[i]==dp[i+1])ans[i]=0;else ans[i]=1;}else{if (a[i]<=f[i+1])ans[i]=1;else ans[i]=2;}if (dp[min(n+1,i+a[i]+1)]!=-1&&i+a[i]<=n)dp[i]=dp[min(n+1,i+a[i]+1)]+1;//更新dp时，满足i+a[i]+1不超区间再加上他也是连续即可更新，否则是-1}maxn[i]=max(maxn[i+1],dp[i]);//更新maxn就是取(i,n)中的dp最大值f[i]=maxn[i+1]+1;//更新f就是你要么修改后最多加一步，要最多，这一步就到max。要么不修改if (a[i]+i+1<=n)f[i]=max(f[i],1+f[i+a[i]+1]);}for (int i=1; i<n; ++i)cout<<ans[i]<<" \\n"[i==n-1];
}
int32_t main()
{std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);ll t;cin >> t;while (t--){mysolve();}system("pause");return 0;
}