本蒟蒻第一次AK周赛
第一题、最大数量
本题使用桶排序
代码
#include<bits/stdc++.h>
using namespace std;
int m[10005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
m[(a*100)+b]++;
}
sort(m,m+2459);
cout<<m[2458];
return 0;
}
第二题、前缀和序列
前置知识:AcWing算法基础课——前缀和
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
int a[N],q[N],b[N],q1[N];
signed main()
{
int n,m;
cin>>n;
q[0]=0;
for(int i=1;i<=n;i++) {cin>>a[i];b[i]=a[i];}
sort(b+1,b+1+n);
cin>>m;
for(int i=1;i<=n;i++) {q[i]=q[i-1]+a[i];q1[i]=q1[i-1]+b[i];}
while(m--){
int s,l,r;
cin>>s>>l>>r;
if(s==1){
cout<<q[r]-q[l-1]<<endl;
}
else cout<<q1[r]-q1[l-1]<<endl;
}
}
第三题、买可乐
第一种方法、暴力
时间复杂度:$O(n)$
#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
LL c, d, n, m, k;
int main() {
cin >> c >> d >> n >> m >> k;
LL need = n * m - k;
if (need <= 0) {
cout << 0 << endl;
return 0;
}
LL ans = 1e18;
for (LL i = 0; i <= 10000; i ++ )
for (LL j = 0; j <= 10000; j ++ )
if (n * i + j >= need)
ans = min(ans, c * i + d * j);
cout << ans << endl;
return 0;
}
第二种方法、贪心
时间复杂度$O(1)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int c, d, n, m, k;
cin >> c >> d >> n >> m >> k;
int cnt = n * m - k;
if (cnt <= 0) puts("0");
else
cout << min({cnt * d, cnt / n * c + cnt % n * d, (cnt + n - 1) / n * c}) << endl;
return 0;
}
标签:周赛,int,namespace,cin,long,using,include,84,AcWing
From: https://www.cnblogs.com/LuoGuyexc/p/17018444.html