• D. The Enchanted Forest


    Problem - D - Codeforces

    思路:一直在正向的考虑,这个题从反向考虑更加容易,首先如果k>=n的话,初始的一定都可以拿完,并且我们知道生长的蘑菇的总量是n*k个蘑菇,那么如果我们知道剩下了多少个蘑菇,那么就能够算出来拿了多少个生长的蘑菇,并且我们期望剩下的蘑菇和越少越好,那么怎么保证最小呢,就是我从最左边一直拿到最右边是最小的此时是1 2 3 4 ... n,那么我们就知道了最后的答案就是sum+n*k-n*(n+1)/2,并且一定存在一种方案使得最后是从左往右拿的,如果k==n+1,那么我们可以从2往左拿,再从1往右拿,同理其他情况也是;如果k最大值,此时拿的生长的蘑菇的数量是k*(k-1)/2;

    1. // Problem: D. The Enchanted Forest
    2. // Contest: Codeforces - Codeforces Round 796 (Div. 2)
    3. // URL: https://codeforces.com/contest/1688/problem/D
    4. // Memory Limit: 256 MB
    5. // Time Limit: 2000 ms
    6. #include
    7. #include
    8. #include
    9. #define fi first
    10. #define se second
    11. #define i128 __int128
    12. using namespace std;
    13. typedef long long ll;
    14. typedef double db;
    15. typedef pair<int,int> PII;
    16. const double eps=1e-7;
    17. const int N=5e5+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7,mod1=998244353;
    18. const long long int llINF=0x3f3f3f3f3f3f3f3f;
    19. inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    20. while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
    21. inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
    22. inline void write(ll x,char ch) {write(x);putchar(ch);}
    23. void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
    24. bool cmp0(int a,int b) {return a>b;}
    25. template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
    26. template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
    27. void hack() {printf("\n----------------------------------\n");}
    28. int T,hackT;
    29. int n,m,k;
    30. int w[N];
    31. ll sum[N];
    32. struct Node{
    33. int l,r;
    34. ll sum;
    35. ll add;
    36. };
    37. Node tr[N*4];
    38. void pushup(int u) {
    39. tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
    40. }
    41. void pushdown(int u) {
    42. if(tr[u].add!=0) {
    43. tr[u<<1].sum+=(ll)(tr[u<<1].r-tr[u<<1].l+1)*tr[u].add;
    44. tr[u<<1|1].sum+=(ll)(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].add;
    45. tr[u<<1].add+=tr[u].add;
    46. tr[u<<1|1].add+=tr[u].add;
    47. tr[u].add=0;
    48. }
    49. }
    50. void build(int u,int l,int r) {
    51. if(l==r) tr[u]={l,r,0,0};
    52. else {
    53. tr[u]={l,r,0,0};
    54. int mid=l+r>>1;
    55. build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    56. }
    57. }
    58. void modify(int u,int l,int r,int c) {
    59. if(tr[u].l>=l&&tr[u].r<=r) {
    60. tr[u].sum+=(ll)(tr[u].r-tr[u].l+1)*c;
    61. tr[u].add++;
    62. }else {
    63. pushdown(u);
    64. int mid=tr[u].l+tr[u].r>>1;
    65. if(l<=mid) modify(u<<1,l,r,c);
    66. if(r>mid) modify(u<<1|1,l,r,c);
    67. pushup(u);
    68. }
    69. }
    70. int query(int u,int l,int r) {
    71. if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
    72. else {
    73. pushdown(u);
    74. int mid=tr[u].l+tr[u].r>>1;
    75. ll res=0;
    76. if(l<=mid) res+=query(u<<1,l,r);
    77. if(r>mid) res+=query(u<<1|1,l,r);
    78. return res;
    79. }
    80. }
    81. void solve() {
    82. n=read(),k=read();
    83. for(int i=1;i<=n;i++) w[i]=read();
    84. for(int i=1;i<=n;i++) sum[i]=sum[i-1]+w[i];
    85. if(n==1) {
    86. printf("%d\n",w[1]+k-1);
    87. return ;
    88. }
    89. if(k>=n) {
    90. ll res=sum[n]+(ll)n*k-(ll)n*(n+1)/2;
    91. printf("%lld\n",res);
    92. }else {
    93. ll res=0;
    94. for(int i=1;i+k-1<=n;i++) {
    95. int l=i,r=i+k-1;
    96. ll temp=sum[r]-sum[l-1]+(ll)k*(k-1)/2;
    97. res=max(res,temp);
    98. }
    99. printf("%lld\n",res);
    100. }
    101. }
    102. int main() {
    103. // init();
    104. // stin();
    105. // ios::sync_with_stdio(false);
    106. scanf("%d",&T);
    107. // T=1;
    108. while(T--) hackT++,solve();
    109. return 0;
    110. }

  • 相关阅读:
    rabbitmq 之 无法自动创建队列的问题
    【Maven】jar包冲突原因与最优解决方案
    力扣爆刷第126天之动态规划五连刷(斐波那契、爬楼梯、不同路径)
    langchain教程-(1)Prompt模板
    Google Earth Engine APP——15行代码搞定一个inspector高程监测APP
    Oracle DBCA建库
    python——单例模式
    RK3568-74HC595
    C++基础知识要点--变量和基本类型
    如何理解MIC?
  • 原文地址:https://blog.csdn.net/zzzyyzz_/article/details/133081914