\(Preface\)
\(Rank46/41\)
\(15pts + 30pts = 45pts\)
\(\mathfrak{T1}\ 乌鸦喝水\)
这个题的题意太坑人了，说的根本不清楚，样例也水，导致我挂成这弔样
他的意思是，乌鸦一共飞\(m\)回合，遇到能喝的就喝，喝了一次之后每个水缸的水位都要下降
直接爆扫有\(25pts\)，及时\(break\)有\(55pts\)，用链表优化爆扫有\(95pts\)
不是你这区分度也太差了吧
正解是树状数组，但是我没写
我去写了迪神的暴力\(dp\)，加点优化，没有水的水缸就不要了，这样可以卡过。感觉和链表差不多，不清楚为什么这个可以过，可能与内存访问连续有关
T1
#include <iostream>
#include <cmath>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ ' '
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define N 100005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL), cerr.tie(NULL);}
/*
二度理解错题意
*/
int n, m, final_ans, mxd;
int w[N], a[N];
void work(){
cin >> n >> m >> mxd;
for (re i = 1 ; i <= n ; ++ i)
cin >> w[i];
for (re i = 1 ; i <= n ; ++ i)
cin >> a[i];
for (re i = 1 ; i <= n ; ++ i)
w[i] = ceil((double)(mxd - w[i] + 1) / a[i]);
/*for (re i = 1 ; i <= n ; ++ i)
cerr << w[i] << _;
cerr << '\n';*/
for (re i = 1 ; i <= m ; ++ i){
for (re j = 1 ; j <= n ; ++ j){
// cerr << i << _ << j << '\n';
if (w[j] <= 0){
continue;
}
for (re k = 1 ; k <= n ; ++ k)
w[k] --;
final_ans ++;
}
}
cout << final_ans << '\n';
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a);
#endif
Fastio_setup();
work();
return GMY;
}
\(\mathfrak{T2}\ kill\)
首先需要明白一件事情：这\(n\)个人打的怪物在\(q\)数组中的下标是连续的。而且哪个人打哪个怪物，也就是打怪物的相对顺序，与人的相对顺序是相同的。比如第一个人打选出来的第一个怪物，第二个人打选出来的第二个怪物...
这个东西，我小证明一下，可能并不严谨
比如\(n=4\)，\(m=5\)有：
1 2 3 \(\mathfrak{4}\) 5 6 7 8 9
其中粗体是怪物，斜体是人，又粗又斜的是人和怪物重合了，那个十分突出的是任务交付点
显然要打第\(2 \sim 4\)个怪物。假如说第一个人去打第一个怪物，显然是比 第一个人打怪物\(2\)，第二个人打怪物\(3\).... 更劣的。
如果你说:“假如任务交付点左边只有一个怪物，而且在人\(1\)的左边呢？”
这个时候方案就变了呗。不可否认的是，选的怪物还是连续的。这个性质用于一会的『枚举起点』。
这个时候“哪个人打哪个怪物，也就是打怪物的相对顺序，与人的相对顺序是相同的。”就不证自明了。这个性质用于一会的『判断距离』。
然后考虑如何求解答案。
首先把\(p\)数组和\(q\)数组升序\(sort\)一下，因为他读入并没有保证有单调性。
因为问的是最晚的人所需时间，所以考虑二分最晚所需时间。
考虑\(check\)函数怎么写。
由于选择的怪物在\(q\)数组中的下标是连续的，所以我们只需要枚举第一个位置是谁，然后向后延伸\(n\)长判断是否打怪所需距离大于\(mid\)即可。
T2
#include <iostream>
#include <algorithm>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout);
#define re register int
#define char_phi signed
#define MARK cout << "###"
#define MARKER "@@@"
#define LMARK "!!!~~~"
#define ZY " qwq "
#define _ ' '
#define Endl cout << '\n'
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define ABS(x) (((x) < 0) ? (-(x)) : (x))
#define N 5005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL), cerr.tie(NULL);}
long long n, m, endplc, final_ans;
long long a[N], b[N];
inline char check(long long mid){
int x = 1;
for (re i = 1 ; i <= n ; ++ i, ++ x){
while (x <= m and ABS(a[i]-b[x])+ABS(b[x]-endplc) > mid)
x ++;
if (x > m)
return false;
}
return true;
}
void work(){
cin >> n >> m >> endplc;
for (re i = 1 ; i <= n ; ++ i)
cin >> a[i];
for (re i = 1 ; i <= m ; ++ i)
cin >> b[i];
sort(a+1, a+n+1); sort(b+1, b+m+1);
long long LF(0), RT(1000000002), mid;
while (LF <= RT){
mid = (LF + RT) >> 1;
if (check(mid) == true)
RT = mid - 1, final_ans = mid;
else
LF = mid + 1;
}
cout << final_ans << '\n';
}
// #define IXINGMY
char_phi main(){
#ifdef IXINGMY
FBI_OPENTHEDOOR(a);
#endif
Fastio_setup();
work();
return GMY;
}