Codeforces Round #437 (Div. 2)[A、B、C、E]

codeforces 867 A. Between the Offices(水)

题意：已知白天所在地（晚上可能坐飞机飞往异地），问是否从西雅图飞到旧金山次数更多。

题解：只要判断第一天和最后一天状态即可。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = ;

 int n;

 char s[N];

 int main() {

     scanf("%d %s", &n, s);

     if(s[] == 'S' && s[n-] == 'F') puts("YES");

     else puts("NO");

     return ;

 }

15ms

codeforces 865 A. Save the problem!(构造)

题意：原本是知道所需钱数和有多少种类的面额以及各面额的价值，要求有多少种方式可以从给定的面额中选取若干拼成所需的钱数，，现在反过来已知多少方式，来构造输入样例。

题解：直接用1和2面额来拼。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n;

 int main() {

     scanf("%d", &n);

     printf("%d 2\n1 2\n", (n-)*+);

     return ;

 }

15ms

codeforces 865 B. Ordering Pizza（贪心）

题意：有两种类型的披萨，已知有N个人要吃披萨，每块披萨有S片；第i个人吃si片，如果吃类型1，每片能获得ai幸福度，吃类型2则是bi幸福度。现在要购买最少数量的披萨满足N个人所需的数量，并求能获得的最大幸福度。

题解：贪心吃幸福度大的类型，记录1、2类型最优各吃几片，如果1、2类型披萨所需数量之和≤总共所需披萨数量，则直接输出答案，否则给 1和2类型幸福度差值较小的赋予高优先级，排序后将多余的1类型换成2类型披萨，或2换成1，以满足最少数量披萨数目。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int N = 1e5+;

 ll n, S;

 ll s[N],a[N],b[N];

 struct node {

     ll x;

     int id;

     bool operator < (const node&r)const{

         return x < r.x;

     }

 }c[N];

 int main() {

     int i, f = ;

     ll ans = , sum = , a1=, a2=;

     ll s1=, s2=;

     scanf("%lld %lld", &n, &S);

     for(i = ; i <= n; ++i) {

         scanf("%lld %lld %lld", &s[i], &a[i], &b[i]);

         if(a[i] > b[i]) s1 += s[i];

         else if(a[i] < b[i]) s2 += s[i];

         sum += s[i];

         ans += max(a[i], b[i]) * s[i];

         c[i].x = a[i] - b[i]; c[i].id = i;

     }

     ll cnt = (sum + S-) /S;

     if((s1 + S-)/S + (s2 + S-)/S <= cnt) {printf("%lld", ans); return ;}

     sort(c+, c++n);

     s1 %= S; s2 %= S;

     for(i = ; i <= n; ++i) {

         if(c[i].x <= ) {f = i; continue;}

         if(!s1) break;

         ll t = min(s[c[i].id], s1);

         a1 += t * c[i].x;

         s1 -= t;

     }

     for(i = f; i >= ; --i) {

         if(!c[i].x) continue;

         if(!s2) break;

         ll t = min(s[c[i].id], s2);

         a2 -= t * c[i].x;

         s2 -= t;

     }

     printf("%lld\n", ans - min(a1, a2));

     return ;

 }

78ms

codeforces 865 D. Buy Low Sell High（优先队列，模拟）

题意：知道N天的股票的价格，一开始有0股，每天可以买一股或卖一股或什么都不做，要在N天后继续是0股，但希望在这N天内赚尽量多的钱。

题解：开个优先队列模拟。注意优先队列默认数据大的优先级高，所以加个负号。

比队首大的值要插入两遍，一是为了给前面小的值升值，二是为了将自己插入队列等待被买入。比如：4、7、9，4被升值为7进而被升值为9（实际选择是-4+9），第二步取出的一个7是为了给4进一步升值，7还要有一个在队列中等待被买入。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 priority_queue<int> q;

 int main() {

     int i, n, x;

     long long ans = ;

     scanf("%d", &n);

     q.push(-);

     for(i = ; i <= n; ++i) {

         scanf("%d", &x);

         if(-q.top() < x) {

             ans += x + q.top(); q.pop(); q.push(-x);

         }

         q.push(-x);

     }

     printf("%lld", ans);

     return ;

 }

108ms

巴特西

Codeforces Round #437 (Div. 2)[A、B、C、E]

最新文章

热门文章