ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[CodeForces]1671.C Dolce Vita(贪心 + 二分 + 容斥原理)

2022年4月24日 1037点热度 0人点赞 0条评论

题目传送门:Problem - C - Codeforces

题目大意

有N个店,每天有X元,每个店 i 每日限购1件,第一天价格为 ai。每个店每天都涨价1元(第一天是原价)。问最终一共最多可以买多少个东西。多组测试用例。

思路

买东西嘛,肯定是越便宜越好(Greedy贪心)。所以先将所有价格排序,在进行一次前缀和,现在第i天购买前j个店的所有商品总价为prefix[j] + i * j。

这时候观察一下数据范围,N <= 2e6,所以可以遍历每前i个店,在固定至少买了i个商品的情况下,通过二分搜索求最多有多少天能至少买i个商品,得到bs[i] = “买的东西 >= i的天数”。

那么恰好购买n个东西的天数 = bs[n] - bs[n + 1]。(容斥原理)

那么答案就是n * bs[n] + (n - 1) * (bs[n - 1] - bs[n]) + ... + 2 * (bs[2] - bs[3]) + bs[1] - bs[2]

整理一下就是bs[1] + bs[2] + ... + bs[n]。

直接记录一下和就好了。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9;
int N, X, a[maxn], prefix[maxn];

int foo(int k)//求最多有多少天可以至少买k个东西 
{
	//右边界位X + 1,不可能买X天以后的东西,因为价格必定大于等于X元 
	int l = 0, r = X + 1;
	while(l + 1 != r)
	{
		int mid = (l + r) >> 1;
		//第mid天买前k个商品的总价 = prefix[k] + k * (mid - 1) 
		if(prefix[k] + k * (mid - 1) <= X)l = mid;
		else r = mid;
	}
	return l;
}


void solve()
{
	cin >> N >> X;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	sort(a + 1,a + 1 + N);
	for(int i = 1;i <= N; ++ i)prefix[i] = prefix[i - 1] + a[i];
	int ans = 0;
	for(int i = 1;i <= N; ++ i)ans += foo(i);
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ codeforeces 二分 容斥原理 算法竞赛 贪心
最后更新:2022年10月17日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号