这里会显示出您选择的修订版和当前版本之间的差别。
2020-2021:teams:die_java:front_page_summertrain14 [2020/08/28 17:07] fyhssgss 创建 |
2020-2021:teams:die_java:front_page_summertrain14 [2020/08/28 21:21] (当前版本) mychael |
||
---|---|---|---|
行 12: | 行 12: | ||
===== A - Xiongnu’s Land ===== | ===== A - Xiongnu’s Land ===== | ||
+ | |||
+ | 将一个矩形区域用一条竖直的线一分为二,使得左边绿洲区域大于等于右边且二者差别尽量小,在此基础上使左边区域尽量大 | ||
=== 题解 === | === 题解 === | ||
- | <hidden 代码><code cpp> | + | 枚举分界点即可 |
+ | <hidden 代码><code cpp> | ||
+ | #include<algorithm> | ||
+ | #include<iostream> | ||
+ | #include<cstdlib> | ||
+ | #include<cstring> | ||
+ | #include<cstdio> | ||
+ | #include<vector> | ||
+ | #include<queue> | ||
+ | #include<cmath> | ||
+ | #include<map> | ||
+ | #include<set> | ||
+ | #define LL long long int | ||
+ | #define REP(i,n) for (int i = 1; i <= (n); i++) | ||
+ | #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt) | ||
+ | #define cls(s,v) memset(s,v,sizeof(s)) | ||
+ | #define mp(a,b) make_pair<int,int>(a,b) | ||
+ | #define cp pair<int,int> | ||
+ | using namespace std; | ||
+ | const int maxn = 1000005,maxm = 100005; | ||
+ | const LL INF = 1000000000000000000ll; | ||
+ | inline int read(){ | ||
+ | int out = 0,flag = 1; char c = getchar(); | ||
+ | while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();} | ||
+ | while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();} | ||
+ | return flag ? out : -out; | ||
+ | } | ||
+ | int N,n; | ||
+ | LL D[maxn],S; | ||
+ | int main(){ | ||
+ | int T = read(); | ||
+ | while (T--){ | ||
+ | N = read(); | ||
+ | n = read(); | ||
+ | S = 0; | ||
+ | int x,y,w,h; | ||
+ | for (int i = 0; i <= N; i++) D[i] = 0; | ||
+ | REP(i,n){ | ||
+ | x = read(); y = read(); w = read(); h = read(); | ||
+ | h = min(h,y); | ||
+ | w = min(w,N - x); | ||
+ | D[x + w] -= h; | ||
+ | D[x] += h; | ||
+ | S += 1ll * w * h; | ||
+ | } | ||
+ | REP(i,N) D[i] += D[i - 1]; | ||
+ | REP(i,N) { | ||
+ | D[i] += D[i - 1]; | ||
+ | //if (i <= 10) printf("%d ",D[i]); | ||
+ | } | ||
+ | //puts(""); | ||
+ | LL mn = INF; | ||
+ | int l = 0; | ||
+ | for (int i = 0; i < N; i++) | ||
+ | if (D[i] >= S - D[i]){ | ||
+ | if (abs(D[i] - (S - D[i])) <= mn){ | ||
+ | mn = abs(D[i] - (S - D[i])); | ||
+ | l = i; | ||
+ | } | ||
+ | } | ||
+ | printf("%d\n",l + 1); | ||
+ | } | ||
+ | return 0; | ||
+ | } | ||
</code></hidden> | </code></hidden> | ||
===== C - Today Is a Rainy Day ===== | ===== C - Today Is a Rainy Day ===== |