郑州大学算法设计与分析实验6

1

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 

using namespace std;
const int N = 2e5+10;
int t; 
struct wy
{
	db w, v, p;
	bool operator < (const wy t) const
	{
		return p > t.p; 
	}
}a[N];
void solve()
{
	int n, k;	cin  >> n >> k;
	rep(i,1,n)	cin >> a[i].v;
	rep(i,1,n)	cin >> a[i].w, a[i].p = a[i].w / a[i].v;
	sort(a+1,a+1+n);
	int pos=0;
	db ans=0;
	rep(i,1,n)
	{
		if(k<=0)	break;
		if(k>=a[i].v)	
		{
			k-=a[i].v;
			ans+=a[i].w;	
		}
		else	
		{
			ans+=a[i].p*k;
			k=0;
		}
	}	
	printf("%.2lf", ans);
}

int main()
{
//	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
	solve();
	return 0;
}

2

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 

using namespace std;
const int N = 2e5+10;
int t; 
int a[N];
void solve()
{
	int n, k; cin >> n >> k;
	rep(i,1,k+1)	cin >> a[i];
	int cur = n, ans=0;
	rep(i,1,k+1)
	{
		if(cur>a[i])	cur-=a[i];
		else	
		{
			cur+=(n-a[i]);
			ans++;
		}
		if(cur<0)
		{
			cout << "No Solution!" << endl;
			return;
		}
	}
	cout << ans << endl;
	
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
	solve();
	return 0;
}

3

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 

using namespace std;
const int N = 2e5+10;
int t; 
struct wy
{
	int l,r;
	bool operator < (const wy t) const
	{
		if(l==t.l)	return r < t.r;
		return l < t.l;
	}
}a[N];
int vis[N];
void solve()
{
	int k; cin >> k;
	rep(i,1,k)	cin >> a[i].l >> a[i].r;
	sort(a+1, a+1+k);
	int ans=0;
	rep(i,1,k)
	{
		
		if(!vis[i])
		{
			int t=i;
			ans++;
			rep(j,i+1,k)
			{
				if(!vis[j] && a[j].l >= a[t].r)
				{
					vis[j]=1;
					t=j;
				}
			}
		}
	}
	cout << ans << endl;
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
	solve();
	return 0;
}

4

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 

using namespace std;
const int N = 2e5+10;
int t; 
int a[N];
void solve()
{
	int n, l; cin >> n >> l;
	rep(i,1,n)	cin >> a[i];
	sort(a+1, a+1+n);
	int ans=0;
	rep(i,1,n)
	{
		if(l>=a[i])
		{
			ans++;
			l-=a[i];
		}
		else
		{
			cout << ans << endl;
			return;
		}
	}
    cout << ans << endl;
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
	solve();
	return 0;
}

5

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 

using namespace std;
const int N = 2e5+10;
int t; 
struct wy
{
	int x,y;
	bool operator < (const wy t) const
	{
		if(x==t.x)	return y>t.y;
		return x > t.x;
	}
}a[N], re[N];
void solve()
{
	int n, m;
	while(cin >> n >> m)
	{
		ll ans=0, price=0, cnt[110]={0};
		rep(i,1,n)	cin >> a[i].x >> a[i].y;
		rep(i,1,m)	cin >> re[i].x >> re[i].y;
		sort(a+1,a+1+n);
		sort(re+1,re+1+m);
		int j=1;
		rep(i,1,m)
		{
			while(j<=n&&re[i].x<=a[j].x)
			{
				cnt[a[j].y]++;
				j++;	
			}
			rep(k,re[i].y,100)
			{
				if(cnt[k]>0)
				{
					cnt[k]--;
					ans++;
					price+=500*re[i].x+2*re[i].y;	
					break;
				}	
			}	
		}
		cout << ans << ' ' << price << endl;
	}
}

int main()
{
	IOS	
//  	freopen("1.in", "r", stdin);
//	cin >> t;
//	while(t --)	
	solve();
	return 0;
}