1. Buying Lemonade
Buying Lemonade
解题思路：
排序：将插槽的罐数 a 从小到大排序（sort(a, a+n)）。
特殊情况处理：
若最小罐数足够大（a[0] >= k/n 且 k%n0）或 k1，直接输出 k（认为每个按钮按 1 次即可，逻辑不严谨）。
贪心遍历：
遍历排序后的插槽，对第 i 个插槽（当前剩余 n-i 个插槽未处理），计算需要按动的次数 len：
len = k/(n-i)（向上取整），表示为了拿到 k 罐，在剩余 n-i 个插槽中，每个至少需要按 len 次。
若 len <= a[i]（当前插槽的罐数足够支持 len 次按动），则直接按 k 次即可拿到足够罐，输出 ans + k。
否则，按动 a[i]+1 次（拿完当前插槽所有罐，再额外按 1 次确保覆盖该插槽），并更新剩余需要的罐数 k -= a[i]。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define endl '\n'
#define pii pair<ll,ll>
#define fi first
#define se second
const ll N=1e6+10;
void solve()
{
ll n,k;
cin>>n>>k;
ll a[n];
for(ll i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
if(a[0]>=k/n&&k%n==0||k==1)
{
cout<<k<<endl;
return ;
}
ll x=0;
ll ans=0;
for(ll i=0;i<n;i++)
{
ll len=k/(n-i);
if(k%(n-i)!=0)
len++;
if(len<=a[i])
{
ans+=k;
break;
}
ans=ans+a[i]+1;
k-=a[i];
}
cout<<ans<<endl;
}
signed main()
{
IOS;
ll t=1;
cin>>t;
while(t--)
solve();
return 0;
}
2. Profitable Interest Rate
Profitable Interest Rate
解题思路：
就是一个数学的推导
如果a>b
直接输出
否则
设最优的为x，a-x>=b-2x;
以此推出：
x>=b-a;
最终代码：
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define endl '\n'
#define pii pair<ll,ll>
#define fi first
#define se second
const ll N=1e6+10;
void solve()
{
ll a,b;
cin>>a>>b;
if(a>=b)
{
cout<<a<<endl;
return ;
}
ll x=b-a;
if(x>=a)
{
cout<<0<<endl;
return ;
}
cout<<2*a-b<<endl;
}
signed main()
{
IOS;
ll t=1;
cin>>t;
while(t--)
solve();
return 0;
}
3. Stalin Sort
Stalin Sort
解题思路：
当且仅当第一个元素最大时，数组是脆弱的。为了证明正向，我们可以在整个范围内执行一次操作，这显然会使数组非递增。现在，我们来证明反向。考虑最大值不是第一个元素的任何数组。注意，对任何子数组进行斯大林排序都不会删除第一个元素，也不会删除最大值。因此，如果第一个元素不是最大值，就会破坏非递增特性，以此只需要找到第一个元素最大的最长子序列
代码：
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define endl '\n'
#define pii pair<ll,ll>
#define fi first
#define se second
const ll N=1e6+10;
ll s[N];
void solve()
{
ll n;
cin>>n;
for(ll i=1;i<=n;i++)
{
cin>>s[i];
}
ll ans=n;
ll sum=0;
for(ll i=1;i<=n;i++)
{
ll cut=0;
for(ll j=i;j<=n;j++)
{
if(s[j]<=s[i])
cut++;
}
sum=max(sum,cut);
}
cout<<ans-sum<<endl;
}
signed main()
{
IOS;
ll t=1;
cin>>t;
while(t--)
solve();
return 0;
}
4. LuoTianyi and the Table
LuoTianyi and the Table
这一题就比较烦了，最开始一直算不出样例，后摸索出来，但是最后求结果时方法不对，结果一直过不了，迫不得已去看题解了。
题解的解题思路非常清晰：
就是构造了两方案，一个是以最大以及次大为主的覆盖，一个覆盖多一个覆盖少，而另一个则是最小以及次小
详细代码：
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define endl '\n'
#define pii pair<ll,ll>
#define fi first
#define se second
void solve()
{
ll n, m;
cin >> n >> m;
ll sum = 0;
ll a[n * m + 1];
for (ll i = 1; i <= n * m; i++) {
cin >> a[i];
}
sort(a + 1, a + n * m + 1);
ll ans = 0;
// 如果行数 n 大于列数 m ，交换 n 和 m ，统一按行数小于等于列数的情况处理
if (n > m)
swap(n, m);
// 计算第一种可能的结果 ans1
// 思路：构建一种表格填充方式，使得最大值和最小值的贡献按特定方式计算
// (n*m - 1) * a[n*m] ：假设最大值 a[n*m] 被 (n*m - 1) 个子表的 max 用到
// a[1] * (n * (m - 1)) ：假设最小值 a[1] 被 n*(m - 1) 个子表的 min 用到
// a[2] * (n - 1) ：假设次小值 a[2] 被 (n - 1) 个子表的 min 用到
ll ans1 = (n * m - 1) * a[n * m] - a[1] * (n * (m - 1)) - a[2] * (n - 1);
// 计算第二种可能的结果 ans2
// 思路：构建另一种表格填充方式，使得最大值和次大值、最小值的贡献按特定方式计算
// (n * (m - 1)) * a[n * m] ：假设最大值 a[n*m] 被 n*(m - 1) 个子表的 max 用到
// a[n * m - 1] * (n - 1) ：假设次大值 a[n*m - 1] 被 (n - 1) 个子表的 max 用到
// a[1] * (n * m - 1) ：假设最小值 a[1] 被 (n*m - 1) 个子表的 min 用到
ll ans2 = (n * (m - 1)) * a[n * m] + a[n * m - 1] * (n - 1) - a[1] * (n * m - 1);
cout << max(ans1, ans2) << endl;
}
signed main()
{
IOS;
ll t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
5.Array merging
Array merging
这一题就属于思路对，但是不会实现
解题思路：
就是找到这两个数组中相同元素的最大连续子段的和就行
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define endl '\n'
#define pii pair<ll,ll>
#define fi first
#define se second
const ll N=1e6+10;
ll a[N];
ll b[N];
void solve()
{
ll n;
cin>>n;
for(ll i=1;i<=n;i++)
cin>>a[i];
for(ll i=1;i<=n;i++)
cin>>b[i];
vector<ll> f1(n+n+1,0);
vector<ll> f2(n+n+1,0);
ll p=1,p1=1;
for(ll i=2;i<=n;i++)
{
if(a[i]!=a[i-1])
{
f1[a[i-1]]=max(f1[a[i-1]],i-p);
p=i;
}
if(b[i]!=b[i-1])
{
f2[b[i-1]]=max(f2[b[i-1]],i-p1);
p1=i;
}
}
f1[a[n]]=max(f1[a[n]],n-p+1);
f2[b[n]]=max(f2[b[n]],n-p1+1);
ll ans=0;
for(ll i=1;i<=n+n;i++)
{
ans=max(ans,f1[i]+f2[i]);
}
cout<<ans<<endl;
}
signed main()
{
IOS;
ll t=1;
cin>>t;
while(t--)
solve();
return 0;
}
总结
还是感觉非常有压力的，而且学到了一种新的思路。