题目链接:http://codeforces.com/contest/867
A. Between the Offices
题意:水题。
解法:直接模拟,判断SF和FS的个数的大小即可。
#include <bits/stdc++.h>
using namespace std;
char s[110];
int main(){
int cnt1=0,cnt2=0;
int n;
scanf("%d",&n);
scanf("%s",s);
int len=strlen(s);
for(int i=0;i<len-1;i++){
if(s[i]=='F'&&s[i+1]=='S'){
cnt2++;
}else if(s[i]=='S'&&s[i+1]=='F'){
cnt1++;
}
}
if(cnt1>cnt2){
puts("YES");
}else{
puts("NO");
}
return 0;
}
B. Save the problem!
题意:给你一个数字A,要你给出一个价格和一堆硬币种类,要让这些硬币组成这个价格的方案数为A
解法:除了A是1的时候,价格都是2*(A-1),硬币只有1和2,因为,你用(A-1)个2元0个1元,然后是(A-2)个2个1元,这样方案数就相当于A-1减到0,共A种。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
if(n==1) printf("1 1\n1\n");
else{
printf("%d 2\n1 2\n",(n-1)*2);
}
return 0;
}
C. Ordering Pizza
题意:一共有两种Pizza,每个Pizza有S片,有n位选手,每位选手吃si片Pizza,其中第一种Pizza吃一片获得的快乐值为ai,第二种为bi。问在保证提供的Pizza个数最小的情况下所能获得的最大的快乐值。
解法:先假定每位选手都吃获得快乐值更大的那种Pizza,并将获得的快乐值差值和所需片数对应记录起来,根据贪心策略求得一个happy值。此时最后需要的Pizz***数一种类为use1,二种类为use2,若两者之和小于S,这说明最后的use1+use2片需要由同一种类提供(保证提供Pizz***数最小)。则用happy值减去min(use1变为二种类提供的happy差值,use2变为一种类提供的happy差值)即为最终答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<pair<LL,LL> >v1,v2;
int N,S;
LL s,a,b;
LL ans,use1,use2;
int main(){
scanf("%d%d",&N,&S);
v1.clear();
v2.clear();
for(int i=1; i<=N; i++){
scanf("%lld%lld%lld",&s,&a,&b);
if(a<b){
ans+=s*b;
use2=(use2+s)%S;
v2.push_back(make_pair(b-a,s));
}else{
ans+=s*a;
use1=(use1+s)%S;
v1.push_back(make_pair(a-b,s));
}
}
if(use1+use2>S){
printf("%lld\n", ans);
return 0;
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
LL a1=0,a2=0;
for(vector<pair<LL,LL> >::iterator it=v1.begin();it!=v1.end();it++){
a1 += min(use1,it->second)*(it->first);
use1 -= min(use1, it->second);
}
for(vector<pair<LL,LL> >::iterator it=v2.begin();it!=v2.end();it++){
a2 += min(use2,it->second)*(it->first);
use2 -= min(use2, it->second);
}
ans -= min(a1, a2);
printf("%lld\n", ans);
return 0;
}
D. Gotta Go Fast
#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
const int maxr = 5005;
double dp[maxn][maxr];//dp[i][j]从第i关到第n关,现在花了j时间的期望
int n,r,s[maxn],f[maxn],top=0;
double p[maxn];
bool check(double t){
for(int i=0; i<=r; i++) dp[n][i]=0;
for(int i=r+1; i<=top; i++) dp[n][i]=t;
for(int i=n-1; i>=0;i--)
for(int j=0;j<=top;j++)
dp[i][j]=p[i]*min(t+f[i],dp[i+1][j+f[i]]+f[i])+(1-p[i])*min(t+s[i],dp[i+1][j+s[i]]+s[i]);
return dp[0][0]>t;
}
int main(){
scanf("%d%d",&n,&r);
top=0;
for(int i=0;i<n; i++){
scanf("%d%d%lf", &f[i],&s[i],&p[i]);
p[i]/=100.0L;
top+=s[i];
}
double l=0, r=1000000000, ans;
for(int i=0; i<100; i++){
long double mid = (l+r)/2.0;
if(check(mid)) ans=mid,l=mid;
else r=mid;
}
printf("%.10f\n", ans);
return 0;
}
E. Buy Low Sell High
题意:我们知道股票每一天的价格,当我们手中没有股票的时候不可以出售,问最后所能获得的最大价值
解法:这个题还真的是奇妙,考虑贪心,用小顶堆维护整个序列。假如当前输入为 x ,且堆空或者堆顶元素大于 x 时,将 x 插入堆中;否则删除堆顶元素,将 x 在堆中插入两遍,这一步的操作含义为:我们买入之前堆顶元素所代表的股票,然后以 x 的价格卖出,此时相当于给之前的元素升值至 x ,再插入的 x 和第一种操作一样。(−4+7−5+9−7+12−2+10=20 ) 统计所有卖出的价值和即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
multiset <int> s;
int main(){
int n, x;
scanf("%d", &n);
LL ans=0;
for(int i=1; i<=n; i++){
scanf("%d", &x);
if(!s.empty()&&x>*s.begin()){
ans += x-*s.begin();
s.erase(s.begin());
s.insert(x);
s.insert(x);
}else{
s.insert(x);
}
}
printf("%lld\n", ans);
return 0;
}