2020-2021:teams:die_java:front_page_summertrain14
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
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 ===== | ||
2020-2021/teams/die_java/front_page_summertrain14.1598605677.txt.gz · 最后更改: 2020/08/28 17:07 由 fyhssgss
