两道题目

2023-10-03 18:43:16

咕咕咕！咕了很久的博客终于更新了！

CF720A Closing ceremony

题目大意

N×M个座位有N×M个人，一开始有 k人在(0,0)点上，l个人在(0,m+1)点上，问是否存在一种方案，使得每个人分配点与起始点的曼哈顿距离小于体力值，且每个人都有位置坐。

思路

贪心，考虑把两个起始点的人尽量往两个角塞

先把第一波人按照体力值从小到大排序

为什么不是从大到小排呢？如果体力值大的人把角落塞满了，体力值小的人又走不远，就没地方去了

然后先把位置先分配前 \(K\) 人（当然也可以先分配给后 \(L\) 人）。为了给后 \(L\) 人留够空间，分配时离 \((0, m+1)\) 点越远越好，若路程相同则选择离起点越远越好。

再分配后 \(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

# include <bits/stdc++.h>

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 ( "[a] %d failed\n", p ); */printf ( "rp++");return 0;}
		/*printf ( "[a] %d : %d, %d\n", p, xx, yy );*/
		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 ) {/*printf ( "[b] %d failed\n", p ); */return 0;}
		/*printf ( "[b] %d : %d, %d\n", p, xx, yy );*/
		used [ xx ] [ yy ] = 1;
        
    }
    
    return 1;
    
}

CF3B Lorry

题目大意

有一个体积为 v 的背包，一共有 n 个物品，每个物品的体积为 ti，价值为 pi 。现要从中取若干物品放入背包，使背包中物品的价值和最大。

思路

贪心。

假设所有的物品都是同一类的，那么显然应该选价值更大的更优，所以对于每一列我们将物品按价值从大到小排序。

枚举体积为 \(1\) 的物品选几个，剩下空间全部放体积为 \(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 ( "%d\n", ans );
    
    for ( int i = 1; i <= pos1; i ++ ) printf ( "%d\n", t1 [ i ].id );
    for ( int i = 1; i <= pos2; i ++ ) printf ( "%d\n", 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

如何使用？

点击下载安装即可

码农公寓

CF720A Closing ceremony

题目大意

思路

Code（请勿Ctrl+C/V）

CF3B Lorry

题目大意

思路

代码

如何使用？

相关文章