首页 > 其他分享 >P10189 [USACO24FEB] Maximizing Productivity B 题解

P10189 [USACO24FEB] Maximizing Productivity B 题解

时间:2024-03-02 09:46:01浏览次数:29  
标签:ch Productivity int 题解 sum read USACO24FEB top define

先说说暴力做法:

每次遍历一遍,看看是否满足 \(t_i + s \le c_i\),满足就计数,不满足就挂。单次时间复杂度显然为 \(O(N)\),总得时间复杂度约为 \(O(NQ)\),TLE是肯定的~

暴力代码

// Problem: Problem 3. Maximizing Productivity
// Contest: USACO - USACO 2024 February Contest, Bronze
// URL: https://usaco.org/index.php?page=viewproblem&cpid=1385
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*Code by Leo2011*/
#include <bits/stdc++.h>

#define log printf
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
#define IOS                      \
	ios::sync_with_stdio(false); \
	cin.tie(nullptr);            \
	cout.tie(nullptr);

using namespace std;

typedef __int128 i128;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 2e5 + 10;
int n, q, c[N], t[N];

template <typename T>

inline T read() {
	T sum = 0, fl = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

template <typename T>

inline void write(T x) {
	static T sta[35];
	int top = 0;
	do { sta[top++] = x % 10, x /= 10; } while (x);
	while (top) putchar(sta[--top] + 48);
}

int main() {
	n = read<int>(), q = read<int>();
	FOR(i, 1, n) c[i] = read<int>();
	FOR(i, 1, n) t[i] = read<int>();
	FOR(i, 1, q) {
		int v = read<int>(), s = read<int>(), cnt = 0;
		FOR(j, 1, n) if (s + t[j] < c[j])++ cnt;
		if (cnt >= v) puts("YES");
		else puts("NO");
	}
	return 0;
}

评测记录,开了优化也只有 20pts。


暴力废了,开始整正解。

\(2 \times 10^5\)?二分法,了解一下?

然后,然后遇到了个问题:二分这东西要求有序,可是 \(c_i\) 与 \(t_i\) 是绑定在一起的啊!咋整?

注意 \(c_i\) 与 \(c_i - t_i\) 没关系,而这个式子能够求出啥啊?想要去到第 \(i\) 个农场最大的 \(S\) 嘛(\(c_i - t_i + t_i = c_i\),刚好卡点儿到,不可能再晚了)!

总结一下,问题相当于预处理出来一个数组 \(a\),使 \(a_i = c_i - t_i\),求数组中是否有至少 \(V\) 个数满足 \(a_i \ge S\)。

先排个序(不然还是 \(O(n)\) 嘛),然后就可以分出来两种做法:

做法一:二分,用 upper_bound函数(因为是大于等于),时间复杂度约为 \(O(QlogN)\)。

做法二:排完序后显然满足 \(a_V \ge a_{V - 1} \ge a_{V - 2} ... a_1\),因此如果 \(a_V\) 都小于等于 \(S\) 了,那它前面的自然也都满足。因此只需要判断 \(a_V \ge S\) 成不成立即可。时间复杂度约为 \(O(Q)\)。

赛时ACCode(做法二):

// Problem: Problem 3. Maximizing Productivity
// Contest: USACO - USACO 2024 February Contest, Bronze
// URL: https://usaco.org/index.php?page=viewproblem&cpid=1385
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*Code by Leo2011*/
#include <iostream>
#include <algorithm>  // 万能头CE

#define log printf
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
#define IOS                      \
	ios::sync_with_stdio(false); \
	cin.tie(nullptr);            \
	cout.tie(nullptr);

using namespace std;

typedef __int128 i128;
typedef long long ll;
typedef pair<int, int> PII;

int N, Q;
int close[200010], t[200010], ans[200010], V, S;

template <typename T>

inline T read() {
	T sum = 0, fl = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}

template <typename T>

inline void write(T x) {
	static T sta[35];
	int top = 0;
	do { sta[top++] = x % 10, x /= 10; } while (x);
	while (top) putchar(sta[--top] + 48);
}

bool x(int a, int b) { return a > b; }

int main() {
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) { cin >> close[i]; }
	for (int i = 1; i <= N; i++) { cin >> t[i]; }
	for (int i = 1; i <= N; i++) { ans[i] = close[i] - t[i]; }
	sort(ans + 1, ans + N + 1, x);
	while (Q--) {
		cin >> V >> S;
		if (ans[V] > S) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

AC记录~

标签:ch,Productivity,int,题解,sum,read,USACO24FEB,top,define
From: https://www.cnblogs.com/leo2011/p/18048321

相关文章

  • ABC295D 题解
    萌萌思维题,但是考场差一点AC。题目等价于寻找区间\([l,r]\)满足数字\(0\)~\(9\)各出现偶数次。根据找筷子这道题的经验,出现偶数次=异或和为\(0\)。但是发现如果和找筷子一样直接异或到一起会出现冲突(例子:$3\oplus5\oplus6=0$)。所以变成二进制数就可以了。......
  • ABC321F 题解
    可撤销背包的模板题。如果没有减操作就是\(01\)背包,众所周知转移方程是\(f[i]=f[i]+f[i-v]\)。考虑减操作,对于一个重量\(i\),不选物品\(v\)的方案数是什么呢?发现我们只需要把选\(v\)的方案去掉就好,那么转移方程就是\(f[i]=f[i]-f[i-v]\)。于是就做完了。注意取模变正......
  • ABC323D 题解
    这个题笔者场上Wa了六次……首先发现一个性质:考虑单个的\(s\),它自己所能合并成的块就是\(c\)的二进制表示。例如当\(s=3,c=7\)时,显然我们可以先两两合并,得到\(3\)个\(s=6\)的,再把其中的两个合并得到一个\(s=12\)的。发现\(7=(111)_2\),正好最终只有三个块:\(s=3,......
  • P3749 题解
    P3749[六省联考2017]寿司餐厅题解发现很少有人讲为什么这题是最大权闭合子图,但作为一个刚学网络流的蒟蒻,我认为考虑是必要的。最大权闭合子图的特点:存在单向依赖关系,选\(x\)必须选\(y\)。每个点只会被选一次。代价有正有负。本问题特点:选一个区间,必选所有子区间(......
  • ABC338G 题解
    ABC338G题解计数题,没有太多思维难度,就是麻烦。显然+和*是比较难搞的,应考虑子问题。复杂度要求线性,考虑每个位置的贡献。Case1:只有数字Ex:1234考虑2的贡献,枚举一下看看。\(12=1\times10+2\times1\)\(123=1\times100+2\times10+3\times1\)\(1234=\dots\)\(2=2......
  • [ABC217F] Make Pair 题解
    [ABC217F]MakePair题解思路解析通过\(n\le200\)和“选出的两个学生离开队列,空出来的位置左右合拢”这两个细节可以想到能用区间dp做,\(f_{i,j}\)表示将\(i\toj\)这个区间全部选完的方案数,然后常规区间dp,加一个判断如果当前区间\([l,r]\)中\(l,r\)是朋友,就可......
  • P4690 [Ynoi2016] 镜中的昆虫 题解
    题目链接:镜中的昆虫经典题了,我们首先回顾下颜色数的常见做法统计:对每个位置维护一个\(pre_i\),表示与当前位置相同的颜色上一次出现位置。那么我们分讨一下。查询\([l,r]\)得到颜色数,对于\(pre_i<l\)的\(i\)点,显然它就是这个区间内\(a_i\)对应颜色出现的第一个位置,我们......
  • window.open 循环下载多个文件会打开新页签问题解决
     批量下载文件,循环使用window.open(url)的方式会打开新页签,参考了一位大侠的文章,使用iframe可以的:https://blog.csdn.net/nanke_yh/article/details/125145717如下:fileList.forEach(file=>{//同时下载多个文件,使用iframe下载,因为window.open或者a......
  • $\text{20240301}$ 字符串练习题解
    \(\text{20240301}\)字符串练习题解一定要写冬令营的题吗?遗憾的。P9717给了一个\(n\)个数的首尾相接的字符串,求若干个操作后能形成的不同的字符串大小。一次操作定义为:将字符串内所有的\(\text{01}\)同时改成\(\text{10}\),如图。通过这张图我们似乎发现了一个规律,这......
  • CF1937D Pinball 题解
    题目链接:https://codeforces.com/contest/1937/problem/D题意简述一个长为n的格子,用'<'或'>'组成的字符串表示,在位置i放一个小球,当前所在位置是'<'则下一秒左移一步,否则下一秒右移一步。小球移动后,之前位置的符号反转,'<'变成'>','>'变成'<',直到小球离开整个......