大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
某商场在一天中一共来了 nn 个客人。
10年积累的网站建设、成都网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站制作后付款的网站建设流程,更有太白免费网站建设让你可以放心的选择与我们合作。每个客人进入商场的具体时刻(精确到分钟)已知。
请你计算并输出在同一时刻(精确到分钟)进入商场的大客人数量。
输入格式
第一行包含整数 nn。
接下来 nn 行,每行包含两个整数 h,mh,m,表示一个客人在 hh 时 mm 分进入商场。
所有时间都按照时间先后顺序给出。
时间采用 2424 小时制。
输出格式
一个整数,表示在同一时刻(精确到分钟)进入商场的大客人数量。
数据范围
前 55 个测试点满足 1≤n≤101≤n≤10。
所有测试点满足 1≤n≤1051≤n≤105,0≤hi≤230≤hi≤23,0≤mi≤590≤mi≤59。
输入样例1:
4
8 0
8 10
8 10
8 45
输出样例1:
2
输入样例2:
3
0 12
10 11
22 22
输出样例2:
1
思路:
第一题向来都是acwing周赛最水的题,这道题也不例外。把小时分钟换成一个数,然后用暴力枚举即可,时间复杂度不高。
具体步骤如下(定义,输入除外):
1.把时间转换为分钟制,就是一个数t。
2.把这个时间对应的数组元素计数, 也就是cnt[t]++,是客人在这个时间来的人数
3.答案不断更新,每次更新为之前的答案与这个时间客人来的人数的大值
4.输出答案
完整代码如下(已AC):
//第84周周赛4788. 大数量
#includeusing namespace std;
int cnt[100001];
int n;
int main()
{
scanf("%d", &n);
int h, m;
int ans = 0;
for(int i = 1; i<= n; i++)
{
scanf("%d%d", &h, &m);
int t = 60 * h + m;
cnt[t]++;
ans = max(ans, cnt[t]);//在同一个点上如果重复就加1,这样就直接算出大值
}
cout<< ans<< endl;
return 0;
}
看完第一题,接下来我们再来看第二题。先看题目:
4789. 前缀和序列给定一个长度为 nn 的正整数序列 a1,a2,…,ana1,a2,…,an。
如果将该序列从小到大排序,则可以得到另一个长度为 nn 的正整数序列 b1,b2,…,bnb1,b2,…,bn。
现在,请你回答 mm 个询问,询问共分为以下两种:
1 l r
,请你计算并输出 ∑i=lrai∑i=lrai。2 l r
,请你计算并输出 ∑i=lrbi∑i=lrbi。输入格式
第一行包含整数 nn。
第二行包含 nn 个正整数 a1,a2,…,ana1,a2,…,an。
第三行包含整数 mm。
接下来 mm 行,每行包含一个询问,格式如题面描述。
输出格式
共 mm 行,每个询问输出一行答案。
数据范围
前 3 个测试点满足 1≤n,m≤10
所有测试点满足 1≤n,m≤,1≤ai≤,1≤l≤r≤n。
输入样例1:
6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6
输出样例1:
24
9
28
输入样例2:
4
5 5 2 3
10
1 2 4
2 1 4
1 1 1
2 1 4
2 1 2
1 1 1
1 3 3
1 1 3
1 4 4
1 2 2
输出样例2:
10
15
5
15
5
5
2
12
3
5
输入样例3:
4
2 2 3 6
9
2 2 3
1 1 3
2 2 3
2 2 3
2 2 2
1 1 3
1 1 3
2 1 4
1 1 2
输出样例3:
5
7
5
5
2
7
7
13
4
思路:运用了前缀和算法(技巧)。
前缀和算法就是优化时间复杂度的一个算法。把每个元素都变成前一个元素数加上当前的。
核心代码如下:
sort(b + 1, b + 1 + n);
for(long long i = 2; i<= n; i++)
{
a[i] = a[i - 1] + a[i];
}
for(long long i = 2; i<= n; i++)
{
b[i] = b[i - 1] + b[i];
}
完整ac代码如下:
//第84周周赛4789. 前缀和序列
#includeusing namespace std;
long long a[100001], b[100001];
long long n, m;
int main()
{
scanf("%lld", &n);
for(long long i = 1; i<= n; i++)
{
scanf("%lld", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + 1 + n);
for(long long i = 2; i<= n; i++)
{
a[i] = a[i - 1] + a[i];
}
for(long long i = 2; i<= n; i++)
{
b[i] = b[i - 1] + b[i];
}
scanf("%lld", &m);
for(long long i = 1; i<= m; i++)
{
long long f;
scanf("%lld", &f);
if(f == 1)
{
long long l, r;
scanf("%lld%lld", &l, &r);
printf("%lld\n", a[r] - a[l - 1]);
}
else
{
long long l, r;
scanf("%lld%lld", &l, &r);
printf("%lld\n", b[r] - b[l - 1]);
}
}
return 0;
}
再来看最后一道题。
4790. 买可乐某商店目前库存可乐数量为 kk 瓶。
可乐的进货价格如下:
请问,为了使得库存可乐数量不低于 n×mn×m 瓶,该商店至少需要花费多少元钱来购进可乐。
显然,当 k≥n×mk≥n×m 时,无需购进可乐。
输入格式
第一行包含两个整数 c,dc,d。
第二行包含两个整数 n,mn,m。
第三行包含整数 kk。
输出格式
一个整数,表示最少花费的金额。
数围范据
前 44 个测试点满足 1≤c,d,n,m,k≤101≤c,d,n,m,k≤10。
所有测试点满足 1≤c,d,n,m,k≤1001≤c,d,n,m,k≤100。
输入样例1:
1 10
7 2
1
输出样例1:
2
输入样例2:
2 2
2 1
2
输出样例2:
0
思路:
一共分为三种情况:
1.全买整箱的
2.全买单瓶的
3.能买整箱买整箱,剩下的零头买单瓶
最后求最小值即可,本题未优化。
完整ac代码如下:
//第84周周赛4790. 买可乐
#includeusing namespace std;
int c, d, m, n, k, xuyao, ans1, ans2, ans3, answer;
int main()
{
cin >>c >>d >>n >>m >>k;
if(k >= m * n)
{
cout<< 0<< endl;
return 0;
}
xuyao = n * m - k;
ans1 = xuyao / n * c + xuyao % n * d;
ans2 = xuyao / n * c + c;
ans3 = xuyao * d;
answer = min(ans3, min(ans1, ans2));
cout<< answer<< endl;
return 0;
}
请您点赞,关注加收藏,谢谢您的阅读!
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧