우 객 다 교 9 - Groundhog Looking Dowdy (척 취)

제목 링크: 클릭 하여 보기
제목: n 일 드 립 니 다. 매일 몇 벌 의 옷 을 선택 할 수 있 지만 매일 한 벌 만 선택 할 수 있 습 니 다. 모든 옷 은 가치 가 있 습 니 다. 지금 은 m 일의 옷 을 골 라 서 최대 치 와 최소 치 의 차 이 를 최소 화해 야 합 니 다.
제목 분석: 경기 할 때 마침 나 누 기 위해 친구 들 이 실수 로 말 실수 한 가짜 알고리즘 을 사용 한 적 이 있다 (나 는 유죄).
경기 후에 문 제 를 보고 문득 깨 달 았 습 니 다. 이것 은 누 드 척 취 가 아니 라 모든 옷 의 가중치 순 서 를 매 긴 다음 에 왼쪽 점, 척 은 오른쪽 점 을 취하 면 됩 니 다. 척 취 의 목 표 는 구간 에 마침 m 개의 옷 이 존재 하 는 것 입 니 다. (이미 순 서 를 정 했 기 때문에 오른쪽 점 이 작 을 수록 좋 습 니 다) 그러면 답 은 node [r] - node [l] 의 최소 치 를 유지 하 는 것 입 니 다.
코드:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;

typedef unsigned long long ull;

const int inf=0x3f3f3f3f;

const int N=1e6+100;

vector>node;

int cnt[N];

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int k;
		scanf("%d",&k);
		while(k--)
		{
			int num;
			scanf("%d",&num);
			node.emplace_back(num,i);
		}
	}
	sort(node.begin(),node.end());
	int r=0,now=0,ans=inf;
	for(int l=0;l

우 객 다 교 9 - Groundhog Looking Dowdy (척 취)

좋은 웹페이지 즐겨찾기