#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int get() {
int x = 0, f = 1;
char c = getchar();
while (!isdigit(c)) {
if (c == '-') {
f = -1;
}
c = getchar();
}
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
const int MaxN = 1005;
const int inf = 0x3f3f3f3f;
const int dx[5] = {0, 1, 0, -1, 0};
const int dy[5] = {0, 0, 1, 0, -1};
int p[MaxN][MaxN], vis[MaxN][MaxN];
int n, m;
int l = inf, r = -inf, mid, ans, f;
bool bfs(int x, int y, int maxn) {
queue<pair<int, int>> q;
q.push({x, y});
vis[x][y] = 1;
while (q.size()) {
int xx = q.front().first;
int yy = q.front().second;
q.pop();
for (int i = 1; i <= 4; i++) {
int nx = xx + dx[i];
int ny = yy + dy[i];
if (nx < 1 || nx > n || yy < 1 || yy > m || vis[nx][ny] || p[nx][ny] > maxn) {
continue;
}
if (nx == n) {
return true;
} else {
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
return false;
}
int main() {
n = get(), m = get();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
p[i][j] = get();
r = max(r, p[i][j]);
l = min(l, p[i][j]);
}
}
while (l <= r) {
mid = (l + r) >> 1;
f = 0;
memset(vis, 0, sizeof(vis));
if (bfs(1, 1, mid)) {
r = mid - 1;
ans = mid;
} else {
l = mid + 1;
}
}
printf("%d", ans);
return 0;
}
P1314
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll n, m, s;
ll y, ans;
ll w[200010], v[200010];
ll l[200010], r[200010];
ll qzh1[200010], qzh2[200010];
bool check(ll wq) {
y = 0;
memset(qzh1, 0, sizeof(qzh1));
memset(qzh2, 0, sizeof(qzh2));
for (int i = 1; i <= n; i++) {
if (w[i] > wq)
qzh1[i] = qzh1[i - 1] + 1, qzh2[i] = qzh2[i - 1] + v[i];
else
qzh1[i] = qzh1[i - 1], qzh2[i] = qzh2[i - 1];
}
for (int i = 1; i <= m; i++) {
int rrrr = r[i];
int llll = l[i];
y += (qzh1[rrrr] - qzh1[llll - 1]) * (qzh2[rrrr] - qzh2[llll - 1]);
}
if (y > s)
return 1;
else
return 0;
}
int main() {
cin >> n >> m >> s;
for (int i = 1; i <= n; i++)
cin >> w[i] >> v[i];
for (int i = 1; i <= m; i++)
cin >> l[i] >> r[i];
int lll = 1;
int rrr = 2000010;
ans = s;
while (lll <= rrr) {
int mid = lll + (rrr - lll) / 2;
if (check(mid))
lll = mid + 1;
else
rrr = mid - 1;
ans = min(ans, llabs(s - y));
}
cout << ans;
}
p4343
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int l, k;
ll arr[100005];
int judge(ll n) {
ll sum = 0;
int sk = 0;
for (int i = 1; i <= l; i++) {
sum += arr[i];
if (sum >= n) {
sk++;
sum = 0;
} else if (sum < 0) {
sum = 0;
}
}
if (sk < k) return 2;
else if (sk > k) return 3;
else return 1;
}
int main() {
cin >> l >> k;
for (int i = 1; i <= l; i++) cin >> arr[i];
ll ansm = -1, ansx = -1;
// 寻找最小值
ll left = 1, right = 1e18;
while (left <= right) {
ll mid = (left + right) / 2;
int res = judge(mid);
if (res == 1) {
ansm = mid;
right = mid - 1;
} else if (res == 2) { // sk <k，mid太大
right = mid - 1;
} else { // res ==3，mid太小
left = mid + 1;
}
}
// 寻找最大值
left = 1, right = 1e18;
while (left <= right) {
ll mid = (left + right) / 2;
int res = judge(mid);
if (res == 1) {
ansx = mid;
left = mid + 1;
} else if (res == 2) { // sk <k，mid太大
right = mid - 1;
} else { // res ==3，mid太小
left = mid + 1;
}
}
if (ansm == -1 || ansx == -1 || ansm > ansx) {
cout << -1 << endl;
} else {
cout << ansm << ' ' << ansx << endl;
}
return 0;
}
p1010
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void divide(int x)
{
bool flag = false; //...判断是否是第一个，如果是的话就不输出加号
while (x != 0)
{
int t = int(log2(x));
/*
log2(x)这个函数求以2为底x的对数，例如log2(8)返回3，因为2^3=8
而这里把返回值强制转换为int是为了找到离x最近又小于x的能表示为2^k的数
例如int(log2(137))就能返回7，而2^7=128，恰为离137最近的能表示为2^k的数
*/
if (flag) cout << "+"; //开头不输出加号
if (t == 1) cout << "2"; //如果这一项是1，输出2，不递归
else if (t == 0) cout << "2(0)"; //如果这一项是0，输出2(0)，不递归
else
{
cout << "2(";
divide(t); //递归一层，把括号里的数分解输出
cout << ")";
}
x -= pow(2,t); //继续处理下一项
flag = true;
}
}
int main() {
int n;
cin >> n;
divide(n);
return 0;
}
p1208
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
struct Compare {
bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
return a.first > b.first; // 小根堆逻辑（第一个元素升序）
}
};
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
int main() {
cin >> n >> m;
int temp1, temp2;
for (int i = 1; i <= m; i++) {
cin >> temp1 >> temp2;
pq.push({temp1, temp2});
}
int sum = 0;
while (n > 0) {
int money = pq.top().first;
int qut = pq.top().second;
if (qut >= n) {
sum += n * money;
break;
} else {
sum += qut * money;
n -= qut;
pq.pop();
}
}
cout << sum;
return 0;
}
p4995
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
ll ans = 0;
int arr[305];
int syb[305];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
memset(syb, 0, sizeof(syb));
int cur = 0;
for (int i = 1; i <= n; i++) {
int max_diff = -1, sid = -1;
for (int j = 1; j <= n; j++) {
if (syb[j] == 0) {
int diff = abs(arr[j] - cur);
if (diff > max_diff) {
max_diff = diff;
sid = j;
} else if (diff == max_diff && arr[j] > arr[sid]) {
sid = j;
}
}
}
syb[sid] = 1;
ans += (ll)max_diff * max_diff;
cur = arr[sid];
}
cout << ans;
return 0;
}
p1199
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[510][510];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)
{
scanf("%d",&a[i][j]);
a[j][i]=a[i][j];
}
int ans=0;
for(int i=1;i<=n;i++)
{
sort(a[i]+1,a[i]+1+n);
ans=ans>a[i][n-1]?ans:a[i][n-1];//选出排名第二中最大的那个
}
printf("1\n%d\n",ans);//一定有解
return 0;
}
p2672
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
pair<int, int> arr[N];
priority_queue<int> pq;
int suffix[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> arr[i].first;
for (int i = 1; i <= n; ++i)
cin >> arr[i].second;
sort(arr + 1, arr + n + 1);
suffix[n + 1] = 0;
for (int i = n; i >= 1; --i) {
suffix[i] = max(suffix[i + 1], 2 * arr[i].first + arr[i].second);
}
int select_id = 0, max_gain = 0;
for (int i = 1; i <= n; ++i) {
if (2 * arr[i].first + arr[i].second > max_gain) {
max_gain = 2 * arr[i].first + arr[i].second;
select_id = i;
}
}
ll sum = max_gain;
int cur_max_s = arr[select_id].first;
cout << sum << endl;
for (int i = 1; i < select_id; ++i) {
pq.push(arr[i].second);
}
int ptr = select_id;
for (int k = 2; k <= n; ++k) {
int right_gain = 0;
if (ptr < n) {
right_gain = suffix[ptr + 1] - 2 * cur_max_s;
}
int left_gain = (pq.empty() ? -1 : pq.top());
if (left_gain >= right_gain) {
sum += left_gain;
pq.pop();
} else {
sum += right_gain;
int new_s = 0, new_id = 0;
for (int i = ptr + 1; i <= n; ++i) {
int val = 2 * arr[i].first + arr[i].second - 2 * cur_max_s;
if (val > new_s) {
new_s = val;
new_id = i;
}
}
cur_max_s = arr[new_id].first;
for (int i = ptr + 1; i < new_id; ++i) {
pq.push(arr[i].second);
}
ptr = new_id;
}
cout << sum << endl;
}
return 0;
}
