A. Water Buying(贪心)

胡乱分析

实际上没有什么难的，如果你用一种方案那么就要用到底，因为这只有两种情况方案一合适或者方案二合适，然后分n的奇偶性来输出即可

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin>>t;
  while(t--)
  {
    long long n,a,b;
    cin>>n>>a>>b;
    if(n&1)
    cout<<min(n*a,(n/2)*b+a)<<"\n";
    else
    cout<<min((n/2)*b,n*a)<<"\n";
  }
}

今天早上我又用刚学的js来了一波，js弱数据类型语言第一次接触对他的判别有点不熟悉导致出现了一个小bug最终也调好了

代码

var n=parseInt(readline());
for(var i=0;i<n;i++)
{
  var s=readline().split(' ');
  if(s[0]%2==0)
  print(Math.min(s[0]*s[1],(s[0]/2)*s[2]));
  else
  print(Math.min(s[0]*s[1],Math.floor(s[0]/2)*s[2]+parseInt(s[1])));
}

B. Tanya and Candies(思维)

胡乱分析

上来寻思了一阵最终得到了和出题人一样的思路奇数偶数项去掉的话奇数偶数会倒置所以根据这个特性来判断即可

代码

#include <bits/stdc++.h>
using namespace std;
long long num[666666];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  long long sum1=0,sum2=0,sum11=0,sum22=0,ans=0,now1=0,now2=0;
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    cin>>num[i];
    if(i&1)
    sum1+=num[i];
    else
    sum2+=num[i];
  }
  sum11=sum1;sum22=sum2;
  for(int i=1;i<=n;i++)
  {
    if(i&1)
    sum1-=num[i];
    else
    sum2-=num[i];
    if(now1+sum2==now2+sum1)
    ans++;
    if(i&1)
    now1+=num[i];
    else
    now2+=num[i];
  }
  cout<<ans;
}

C. Palindromic Matrix(数学&&模拟)

这个题目前还有争议主要就是出的有点复杂并且难度有点高，我现在也没有搞懂

D1. Coffee and Coursework (Easy version)(贪心)

胡乱分析

当时有点贪心的太容易了导致了wa，我最初想的是要都喝了然后如果不行留下当前天数的喝的数然后再继续循环喝完的操作但是实际上只留下一杯是远远的不够贪心的这里用一种非常简单的方法即可枚举出来留下合适的杯数

1
2
3

for(int i=1;i<=n;i++)
for(int j=0;j<n;j++)
sum+=max(0,num[j]-j/i);

看着是非常的奇怪但是实际上这种方法能够保证计算出最优的答案，因为j如果不是i的倍数那么会一直累加到之前的天数上并且发生了自己应当的变化
真的太美妙了！！！

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n,m;
  cin>>n>>m;
  vector<int> num(n+10);
  for(int i=1;i<=n;i++)
  cin>>num[i];
  sort(num.rbegin(),num.rend());
  for(int i=1;i<=n;i++)
  {
    int sum=0;
    for(int j=0;j<n;j++)
    sum+=max(0,num[j]-j/i);
    if(sum>=m)
    return cout<<i,0;
  }
  cout<<-1;
}

D2. Coffee and Coursework (Hard Version)(贪心&&二分)

胡乱分析

跟第D1不一样的地方就是限制了O(n²)的算法，那么对于这种能够靠条件判断出范围的问题我们可以用二分搜索来减少时间复杂度
这里也是又对二分有了一些理解并且也准备以后按照MikeMirzayanov的写法进行书写

while(r-l>precision) //这里的precision是一个精度可以如果是整数那么就是1，小数的话保留小数位数向上一位即可
{
  int mid=(l+r)>>1; //如果是小数的话改成double
  if(check(mid))
  //转换边界
  else
  //转换边界

  //这里的转换边界看是要求一个范围内的最小值还是最大值，最小值的话就是缩小右边界否则就是缩小左边界
}

代码

#include <bits/stdc++.h>
using namespace std;
vector<int> num(666666);
int n,m;
int check(int x)
{
  long long sum=0;
  for(int i=0;i<n;i++)
  sum+=max(0,num[i]-i/x);
  return sum>=m;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  cin>>num[i];
  sort(num.rbegin(),num.rend());
  int l=1,r=n;
  while(r-l>1)
  {
    int mid=(r+l)>>1;
    if(check(mid))
    r=mid;
    else
    l=mid;
  }
  if(check(l))
  cout<<l;
  else if(check(r))
  cout<<r;
  else
  cout<<-1;
}