Kajaki – Omówienie zadania z finału Olimpiady Informatycznej Licealistów

Kajaki – Omówienie zadania z finału Olimpiady Informatycznej Licealistów

Szczegółowe omówienie zadania Kajaki.
Finał Olimpiady Informatycznej Licealistów:

Link do powyższego omówienia zadania Kajaki:
Zadanie Kajaki wymaga jedynie prostego spostrzeżenia!
Zadanie pochodzi z odległej edycji Olimpiady Informatycznej, tym niemniej jest bardzo motywujące!
Zadanie Kajaki pochodzi z finału IV Olimpiady Informatycznej Licealistów:
https://szkopul.edu.pl/task_archive/oi/
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
———

#include<bits/stdc++.h>
using namespace std;

constexpr int M=3e4+7;

int t[M];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n,w,res,k; 
	
	cin >> w >> n;
	
	res = n;
	k = n-1;
	
	for(int i=0; i<n; i++) cin >> t[i];
	sort(t,t+n);
	
	for(int i=0; i<n; i++){
		while(1){
			if( k <= i ) break;
			if( t[k] + t[i] <= w ){
				res--;
				k--;
				break;
			}
			if( t[k] + t[i] > w ) k--;
		}
	}
	
	cout << res;
	return 0;
}
Kod C++ programu Kajaki, który realizuje przedstawiony w omówieniu pomysł i który otrzymuje 100% 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz