Codeforces 1279(A，B，C，D) round79(rated for Div.2 )

本文主要是介绍Codeforces 1279(A，B，C，D) round79(rated for Div.2 )，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

A. New Year Garland

题意：将r个红灯和g个绿灯b个蓝灯串成一串，如果能使相邻两个灯不同色就输出YES，否则输出NO。（开头和结尾可以同色）。

思路：简单的思路，个数最多的灯max，个数最少的灯min，个数居中的灯mid。只要是(max-min)>mid+1;就是合法的方案。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=2*1e5+5;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--){int r,g,b;cin>>r>>g>>b;if(r<g){int t=r;r=g;g=t;}if(r<b){int t=r;r=b;b=t;}if(g<b){int t=g;g=b;b=t;}if(r-b>g+1)cout<<"NO"<<endl;else cout<<"YES"<<endl;}return 0;
}

B. Verse For Santa

题意：Vasya要在圣诞老人面前背诵n段诗歌，第i段需要花费ai分钟，圣诞老人给他s分钟背诵，背诵了多少段可以得到多少个礼物，期间可以跳过一段（全程只能跳一段或不跳）来获取更多的礼物。如果需要跳，输出被跳段落的地址，否则输出0.

思路：这个题我首先想到的就是用结构体来做，用id表示第i个位置以前的做大值地址，用ma来表示这个最大值，用su来表示背诵前i段需要的总时间。
再倒着遍历找到某个位置的su-ma<=s，输出这个位置的最大值id就行。（没想到这种方法还能过，哈哈~）

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=2*1e5+5;
struct node{ll su,ma,id;
}a[MAXN];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t;cin>>t;while(t--){int n,s; cin>>n>>s;int tmp,maxx=-INF;for(int i=1;i<=n;i++){cin>>tmp;if(i==1){maxx=tmp;a[i].su=tmp;a[i].ma=tmp;a[i].id=i;}else{a[i].id=a[i-1].id;if(tmp>maxx){maxx=tmp;a[i].id=i;}a[i].ma=maxx;a[i].su=a[i-1].su+tmp;}}
//        for(int i=1;i<=n;i++){
//            cout<<a[i].su<<" "<<a[i].ma<<" "<<a[i].id<<endl;
//        }for(int i=n;i>0;i--){if(i==n&&a[i].su<=s){cout<<0<<endl;break;}if(a[i].su>s&&a[i].su-a[i].ma<=s){cout<<a[i].id<<endl;break;}}}return 0;
}

C. Stack of Presents

题意：圣诞老人手上有n个礼物（乱序），需要按一定顺序送出m个礼物。第一个礼物如果在n个礼物中的i位置，那么他需要取出前面i-1个礼物才能送出礼物i，并且还需要把前i-1个礼物排序（使下一个需要送出的礼物用时最少，即在第一个位置）后放回去。计算送出这m个礼物总共需要花费的最少时间？

思路：标记第一个礼物在n个礼物中的位置为pose，若后面的礼物在它之前，则time+=1（因为前面的排序必定是最优的方案），若后面的礼物在它之后，用时time+=2*（i-1）+1,并且更新pose的值。（但是需要注意答案的数据范围）

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=2*1e5+5;
int a[MAXN],b[MAXN],d[MAXN];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll n,m,t;cin>>t;while(t--){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];d[a[i]]=i;}ll ans=0,pose=-1;for(int i=1;i<=m;i++){cin>>b[i];if(d[b[i]]>pose) ans+=2*(d[b[i]]-i)+1,pose=d[b[i]];else ans++;}cout<<ans<<endl;}return 0;
}