Educational Codeforces Round 143 (Rated for Div. 2)\C_Tea_Tasting.cpp
//题意：有n种茶，n个人，第i种茶有 a[i]的量，第i个人一次能喝 b[i], 第i个人从第i种茶开始往前喝，求每个人最多能喝多少茶。
//思路：纯模拟时间超限，对于a数组中的每个元素，他要减的是包括i在内以及其右边的b数组中的元素，
//那么需要先求出b数组的前缀和数组sum，那么对于任意的ai,我们可以找到它从i向右减b中元素后第一次减成0的位置
//也就是在前缀和数组中从i向右的位置二分查找第一个sum[j]-sum[i-1]>ai的位置j，从i到j-1的每一个b中元素都是使ai减去一个完整的自己的，
//bj使ai减剩下的数减到了0，用差分数组cnt记录b中每个元素使a中元素减去了几个完整的自己也就是对于每次二分查找，都有cnt[i]++,cnt[j]--，
//然后用另一个数组ex记录b中每个数使a中某个数减到零所提供的贡献，n次二分查找结束后，对差分数组求前缀和，答案数组就等于cnt[i]*b[i]+ex[i]
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
using namespace std;
#define endl '\n'
typedef pair<int,int> pr;
#define int long long
#define ll long long
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define ufr(i,n,z) for(int i = n;i >= z; i--)
#define pb(x) push_back(x)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
const int N = 1e6+10;
const int mod=998244353,inf=LONG_LONG_MAX;
int n,m;
int a[N];
int b[N];
int sum[N];
int ex[N];
void solve(){
/* cin>>n;
fr(i,1,n){
cin>>a[i];
c[i]=0;
}
fr(i,1,n){
cin>>b[i];
}
fr(i,1,n){
ufr(j,i,1){
c[i]+=min(a[j],b[i]);
if(b[i]>=a[j]){
a[j]=0;
}
else{
a[j]-=b[i];
}
}
}
fr(i,1,n){
cout<<c[i]<<' ';
}
cout<<'\n'; */
int n;
cin>>n;
fr(i,1,n){
cin>>a[i];
sum[i]=0;
ex[i]=0;
}
fr(i,1,n){
int x;
cin>>x;
b[i]=b[i-1]+x;
}
fr(i,1,n){
int it=upper_bound(b+1,b+1+n,b[i-1]+a[i])-b; //后面的a不用减前面的b,整体基础上+b[i-1]
//cout<<it<<' ';
sum[i]++;
sum[it]--;
ex[it]+=a[i]-(b[it-1]-b[i-1]);
}
//cout<<'\n';
fr(i,1,n){
sum[i]+=sum[i-1];
}
fr(i,1,n){
cout<<sum[i]*(b[i]-b[i-1])+ex[i]<<' ';
}
cout<<'\n';
}
signed main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}Codeforces Round 887 (Div. 2)\C_Ntarsis_Set.cpp
//题意:n个数，每次按照顺序删除位于a[i]位置的这n个数，问k次后最小的是多少
//思路：如果没有1，则最小为1，有1通过列举情况可以发现对于某一个删除位，前面有几个删除位，后面就要跳几次删，
//于是发现这是一个公差为1，2,3...不断变化的n个数列，第i个数列截止与a[i+1],为了防止没有k个数，于是增加一个公差为n+1,截止于1e18的数列
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
using namespace std;
#define endl '\n'
typedef pair<int,int> pr;
#define int long long
#define ll long long
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define ufr(i,n,z) for(int i = n;i >= z; i--)
#define pb(x) push_back(x)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
const int N = 1e6+10;
const int mod=998244353,inf=LONG_LONG_MAX;
int a[N];
void solve()
{
int n,k;
cin>>n>>k;
fr(i,1,n){
cin>>a[i];
}
if(a[1]!=1){
cout<<1<<'\n';
return;
}
a[n+1]=inf; //保证一定有k个数
vector<int>v;
int cnt=1;
int d=1;
fr(i,2,n+1){
while(cnt+d<a[i]){
cnt+=d;
v.push_back(cnt);
if(v.size()>k+1){
break;
}
}
if(v.size()>k+1){
break;
}
d=i;
}
cout<<v[k-1]<<'\n';
}
signed main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}\Codeforces Round 842 (Div. 2)\C_Elemental_Decompress.cpp
//题意：给定一个长度为n的排列a，请构造两个数组 p,q，要求 max(pi,qi)=ai，并且两个数组都是排列，请输出两个数组。
//思路：1.对于出现三次及以上的NO,对于出现两次的一定有没出现出现的与之对应，否则NO文章来源：https://www.toymoban.com/news/detail-616981.html
//2.将出现两次的与没出现的对应，没出现的记录，在记录寻找首次小于出现两次的对应，下一次再出现颠倒位置，文章来源地址https://www.toymoban.com/news/detail-616981.html
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
using namespace std;
#define endl '\n'
typedef pair<int,int> pr;
#define int long long
#define ll long long
#define fr(i,l,r) for(int i=l;i<=r;i++)
#define ufr(i,n,z) for(int i = n;i >= z; i--)
#define pb(x) push_back(x)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
const int N = 1e6+10;
const int mod=998244353,inf=LONG_LONG_MAX;
int n,m;
int a[N];
int ans1[N];
int ans2[N];
void solve(){
cin >> n;
for (int i = 1; i <= n; i++ ) cin >> a[i];
map<int, int> mp, st;
for (int i = 1; i <= n; i++ ) {
mp[a[i]]++ ;
if(mp[a[i]] > 2){
cout<<"NO"<<'\n';
return ;
}
}
int cur = 0;
vector<int> v;
for (int i = 1; i <= n; i++ ) {
cur += mp[i];
if(!mp[i]) v.push_back(i);
if(cur > i){
cout<<"NO"<<'\n';
return;
}
}
cout << "YES" << endl;
for (int i = 1; i <= n; i++ ) {
if(mp[a[i]] == 1) {
ans1[i] = a[i];
ans2[i] = a[i];
continue;
}
if(!st[a[i]]) {
auto it = lower_bound(v.begin(), v.end(), a[i]);
if(it == v.begin()) { //没有小的
cout<<"NO"<<'\n';
return ;
}
it-- ;
ans1[i] = *it;
st[a[i]] = ans1[i];
ans2[i] = a[i];
v.erase(it); //还要删除防止重复
} else {
ans1[i] = a[i];
ans2[i] = st[a[i]];
}
}
for (int i = 1; i <= n; i++ )
cout << ans1[i] << " \n"[i == n];
for (int i = 1; i <= n; i++ )
cout << ans2[i] << " \n"[i == n];
}
signed main()
{
int t=1;
cin>>t;
while(t--) solve();
return 0;
}到了这里，关于2020/7/30的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
