2020-2021:teams:namespace:牛客多校第八场
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:namespace:牛客多校第八场 [2020/08/08 20:47] great_designer |
2020-2021:teams:namespace:牛客多校第八场 [2020/08/08 20:55] (当前版本) great_designer |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| 参考题解的答案是：总点数-#（k个点， k-1条边的连通分量） | 参考题解的答案是：总点数-#（k个点， k-1条边的连通分量） | ||
| - | |||
| - | |||
| <hidden> | <hidden> | ||
| 行 207: | 行 205: | ||
| </hidden> | </hidden> | ||
| + | =====K===== | ||
| + | 本来在赛场上我已经几乎把这个题分析完了，只是觉得维护太麻烦，可能会用到线段树之类（不会），就没写。 | ||
| + | |||
| + | 然后看到这份代码，觉得这就是个暴力…… | ||
| + | |||
| + | <hidden> | ||
| + | <code C> | ||
| + | |||
| + | #include<stdio.h> | ||
| + | |||
| + | int T; | ||
| + | long long Max[101000]; | ||
| + | long long a[101000]; | ||
| + | int b[101000]; | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | scanf("%d",&T); | ||
| + | int tt; | ||
| + | for(tt=1;tt<=T;tt++) | ||
| + | { | ||
| + | int n; | ||
| + | scanf("%d",&n); | ||
| + | long long now = 0; | ||
| + | Max[0] = -1e10; | ||
| + | int i; | ||
| + | for(i = 1; i <= n; i++) | ||
| + | { | ||
| + | scanf("%lld", &a[i]); | ||
| + | now += a[i];//前缀和 | ||
| + | Max[i]=Max[i-1]>now?Max[i-1]:now;//求当前最大利润 | ||
| + | } | ||
| + | unsigned long long ans1 = 0, ans2 = 0;//开两个的原因是unsigned long long不能出现负数，为了解决用两个unsigned long long来存值，一个存负值，一个存正值 | ||
| + | int w; | ||
| + | for(i = 1; i <= n + 1; i++) | ||
| + | { | ||
| + | if(i <= n) | ||
| + | { | ||
| + | scanf("%d", &b[i]); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | b[i] = 0; | ||
| + | } | ||
| + | if(i == 1) | ||
| + | { | ||
| + | w = b[1]; | ||
| + | } | ||
| + | if(b[i] < w) | ||
| + | { | ||
| + | if(Max[i - 1] < 0) | ||
| + | { | ||
| + | ans2 += (unsigned long long)(-Max[i - 1]) * (w - b[i]); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | ans1 += (unsigned long long)Max[i - 1] * (w - b[i]); | ||
| + | } | ||
| + | w = b[i];//用了w-b[i]个，剩下了b[i]个，最后有个b[n+1]=0收尾，不重不漏 | ||
| + | } | ||
| + | } | ||
| + | if(ans1 < ans2) | ||
| + | { | ||
| + | printf("Case #%d: %d -%llu\n", tt, b[1], ans2 - ans1); | ||
| + | } | ||
| + | else | ||
| + | { | ||
| + | printf("Case #%d: %d %llu\n", tt, b[1], ans1 - ans2); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/namespace/牛客多校第八场.1596890840.txt.gz · 最后更改: 2020/08/08 20:47 由 great_designer
