GPA

NC216041. GPA

描述

In this term, Alice took $n$ courses. Now, she has finished all final exams, and she will get her grades in the following $n$ days.

On the i-th day, Alice will know her grade of the i-th course, denoted as $A_i$ . If $A_i$ is strictly less than the average grade of the first $i-1$ courses, Alice will be sad on that day.

Now Bob hacks into the school's database. Bob can choose a set $S$ of courses ( $S$ can be empty), and then for each course $i$ in $S$ , change Alice's grade from $A_i$ to $B_i$ .

Bob wants to minimize the number of days that Alice will be sad. Now you need to help him to decide which courses' grades he should modify.

Note: Alice is always happy on the first day.

输入描述

The first line contains one single integer .

Then  lines follow. The i-th line contains 2 integers .

The input guarantees that ，.

输出描述

Output the minimum number of the days that Alice will be sad.

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 52ms, 内存消耗: 63484K, 提交时间: 2020-12-26 20:55:51

#include<bits/stdc++.h>
using namespace std;
int INF=0x3f3f3f3f;
int n;
int a[4010],b[4010]; 
int f[4010][4010];//f[i][j]表示截止到第i天，j次不开心次数的当前值 
int main()
{
	cin>>n;
	memset(f,INF,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<i;j++)
		{
			int p;
			p= f[i-1][j]>(i-1)*a[i];
			f[i][j+p]=min(f[i][j+p],f[i-1][j]+a[i]);
			p= f[i-1][j]>(i-1)*b[i];
			f[i][j+p]=min(f[i][j+p],f[i-1][j]+b[i]);
		} 
	}
	for(int i=0;i<n;i++)
	{
		if(f[n][i]<INF)
		{
			cout<<i;
			return 0;
		}
	}
	return 0;
}