> 咕咕咕！咕了很久的博客终于更新了！
CF720A Closing ceremony 题目大意> N×M个座位有N×M个人，一开始有 k人在(0,0)点上，l个人在(0,m+1)点上，问是否存在一种方案，使得每个人分配点与起始点的曼哈顿距离小于体力值，且每个人都有位置坐。
思路贪心，考虑把两个起始点的人尽量往两个角塞
先把第一波人按照体力值从小到大排序
> 为什么不是从大到小排呢？如果体力值大的人把角落塞满了，体力值小的人又走不远，就没地方去了
然后先把位置先分配前 K K K 人（当然也可以先分配给后 L L L 人）。为了给后 L L L 人留够空间，分配时离 ( 0 , m + 1 ) (0, m+1) (0,m+1) 点越远越好，若路程相同则选择离起点越远越好。
再分配后 L L L ，离起点越远越好。
若可行区间内节点都已选择，输出“NO”，否则输出“YES”。
（PS：这道题的算法标签为什么是排序、队列？？？）
Code（请勿Ctrl+C/V）// Problem: CF720A Closing ceremony // URL: https://www.luogu.com.cn/problem/CF720A // Memory Limit: 250 MB // Time Limit: 2000 ms // Author: arlenWKX # includeCF3B Lorry 题目大意using namespace std; const int NM = 10005; int n, m, k, l, a [ NM ], b [ NM ]; bool used [ NM ] [ NM ]; bool __CF720A__ ( ); int main ( ) { scanf ( "%d%d", & n, & m ); scanf ( "%d", & k ); for ( int i = 1; i <= k; i ++ ) scanf ( "%d", & a [ i ] ); scanf ( "%d", & l ); for ( int i = 1; i <= l; i ++ ) scanf ( "%d", & b [ i ] ); sort ( a + 1, a + k + 1 ); //sort ( b + 1, b + l + 1 ); if ( __CF720A__ ( ) ) printf ( "YES" ); else printf ( "NO" ); return 0; } bool __CF720A__ ( ) { for ( int p = 1; p <= k; p ++ ) { int xx, yy, ans1 = -1, ans2 = -1; for ( int i = 1; i <= n; i ++ ) for ( int j = 1; j <= m; j ++ ) if ( ! used [ i ] [ j ] && i + j <= a [ p ] ) { if ( i + m - j > ans1 ) ans1 = i + m - j, ans2 = i + j, xx = i, yy = j; else if ( i + m - j == ans1 && i + j > ans2 ) ans1 = i + m - j, ans2 = i + j, xx = i, yy = j; } if ( ans2 == -1 ) {printf ( "rp++");return 0;} used [ xx ] [ yy ] = 1; } for ( int p = 1; p <= l; p ++ ) { int xx, yy, ans2 = -kidding_you; for ( int i = 1; i <= n; i ++ ) for ( int j = 1; j <= m; j ++ ) if ( ! used [ i ] [ j ] && i + m + 1 - j <= b [ p ] ) { if ( i + m - j + 1 > ans2 ) ans2 = i + m + 1 - j, xx = i, yy = j; } if ( ans2 == -1 ) {return 0;} used [ xx ] [ yy ] = 1; } return 1; }
> 有一个体积为 v 的背包，一共有 n 个物品，每个物品的体积为 ti，价值为 pi 。现要从中取若干物品放入背包，使背包中物品的价值和最大。
思路贪心。
假设所有的物品都是同一类的，那么显然应该选价值更大的更优，所以对于每一列我们将物品按价值从大到小排序。
枚举体积为 1 1 1 的物品选几个，剩下空间全部放体积为 2 2 2 的物品，取价值的最大值即可。
代码// Problem: CF3B Lorry
// URL: https://www.luogu.com.cn/problem/CF3B
// Memory Limit: 62.50MB
// Time Limit: 2000 ms
// Author: arlenWKX
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, v, cnt1, cnt2, pos1, pos2, ans, sum, pre [ N ];
struct wtf
{
int p, id;
bool operator < ( const wtf & b ) const
{ return p > b.p; }
} t1 [ N ], t2 [ N ];
int main ( )
{
scanf ( "%d%d", & n, & v );
for ( int i = 1; i <= n; i ++ )
{
int t, p;
scanf ( "%d%d", & t, & p );
if ( t == 1 ) t1 [ ++ cnt1 ] = { p, i };
else t2 [ ++ cnt2 ] = { p, i };
}
sort ( t1 + 1, t1 + cnt1 + 1 );
sort ( t2 + 1, t2 + cnt2 + 1 );
for ( int i = 1; i <= cnt2; i ++ ) pre [ i ] = pre [ i - 1 ] + t2 [ i ].p;
for (int i = 0; i <= min ( v, cnt1 ); i ++ ) {
sum += t1[i].p;
if ( sum + pre[min(cnt2, (v - i) / 2)] > ans )
{
ans = sum + pre[min(cnt2, (v - i) / 2)];
pos1 = i, pos2 = min(cnt2, (v - i) / 2);
}
}
printf ( "%dn", ans );
for ( int i = 1; i <= pos1; i ++ ) printf ( "%dn", t1 [ i ].id );
for ( int i = 1; i <= pos2; i ++ ) printf ( "%dn", t2 [ i ].id );
return 0;
}
以下内容与题目无关
安利一个超好用的编辑器 —— CP Editor，
（咦？这是Win11？）
> 大家熟知的那些 IDE 往往都是为工程开发而设计的，所以在算法竞赛中用起来多少会有些不顺手的地方，想要却没有的 feature。在这些 IDE 中，Dev C++ 是不怎么配置就比较适合 OI 的，而 VS Code 在经过繁杂的配置后可以更加好用。但是，有没有一款 IDE，既不需要繁杂的配置，又能在 OI 这个领域中，在某些方面上，甚至胜过 VS Code 呢？
> CP Editor
> CP Editor 是一款专门为算法竞赛设计的 IDE，有一键编译并在测试数据上运行，从 OJ 获取样例，在 IDE 内提交至 CF，代码模板等功能。它是一款刚诞生不久的自由软件，以后还会变得越来越好。这款 IDE 是跨平台的，支持 Windows, Linux, MacOS。
> GitHub Repo
点击下载安装即可
