[nk] 牛客练习赛97 C.哦~唔西迪西小姐~ 反悔贪心练手题

前言

传送门 :

题意

思路

一开始以为是带参数的 b f s bfs bfs或者 d p dp dp 但是发现两者都不好解决,因此只能贪心了

对于每次走的格子,如果当前格子的状态和正在走的状态一致,我们考虑直接计入答案,当然还需要将改变当前格子的答案放入队列中

否则是必须改变的,我们直接加入队列中即可

最后在贪心的从队列中拿取 m m m个即为答案

很不错的一个反悔贪心练手题

Mycode

// Problem: 哦~唔西迪西小姐~
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11187/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;
const int N = 1e5+10;
int a[N],p[N];
int st[N];
int n,m;

void solve(){
	cin>>n>>m;
	for(int i=1;i>a[i],a[i] = max(a[i],0);
	for(int i=1;i>p[i];//改变需要的费用
	for(int i=1;i>st[i];//当前格子的在状态
	ll ans =0 ;
	
	for(int k=0;k