QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#404604#2544. Flatland CurrencyZxc200611WA 117ms10580kbC++142.6kb2024-05-04 10:34:082024-05-04 10:34:09

Judging History

你现在查看的是最新测评结果

  • [2024-05-04 10:34:09]
  • 评测
  • 测评结果:WA
  • 用时:117ms
  • 内存:10580kb
  • [2024-05-04 10:34:08]
  • 提交

answer

/*
5 及以上的面额没用。
有 c1 个 1 元和 c5 个 5 元。
每次可以花任意硬币买一件商品,设需要找 x 元则会找 x/5 个 5 元与 x%5 个 1 元硬币。
要使最后 1 元硬币尽量多。

若付的钱已足够,则多付 1 元与 5 元都是不优的。
用纯 1 元买东西肯定不优。
对于一件价格为 x 的商品,若 c5 >= ceil(x/5),
	则可以花这么多 5 元换取 (-x)%5 个 1 元。
若 5 元不够,则额外花 1 元肯定也不优。
也就是说,只会花 5 元硬币来换 1 元。

在只花 5 元的情况下,一定单买物品吗?
两个物品 x、y。
	若 x%5+y%5 > 5,则不会减少需要的 5 元数量。没有用。
	否则,不如只买 x。

相当于,有一些商品,每个有价格,以及 0~4 的价值。你有 c5 的钱,求可以买到多少价值。
交换两维。设 f[i][x] 表示考虑价值小于等于 i 的物品,获得 x 的价值需要花费多少钱。
价值相同的物品肯定按价格从小到大选。对相同的余数有决策单调性?
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x1f1f1f1f1f1f1f1f;
int n,c,c1,c5;
int f[2][410000];
vector<int> v[5];
void devideConquer(int i,int r,int ql,int qr,int al,int ar)
{
	// cout<<"DevideConquer q=["<<ql<<","<<qr<<"] a=["<<al<<","<<ar<<"]"<<endl;
	if(ql>qr)
		return;
	int qm=((ql/i+qr/i)/2)*i+r;
	// cout<<"qm="<<qm<<endl;
	int pos=-1;
	for(int x=max<int>(al,qm-i*(v[i].size()-1));x<=min<int>(qm,ar);x+=i)
	{
		if(pos==-1||f[0][x]+v[i][(qm-x)/i]<=f[0][pos]+v[i][(qm-pos)/i])
			pos=x;
	}
	assert(pos!=-1);
	f[1][qm]=f[0][pos]+v[i][(qm-pos)/i];
	devideConquer(i,r,ql,qm-i,al,pos);
	devideConquer(i,r,qm+i,qr,pos,ar);
}
signed main()
{
	cin>>n>>c;
	c5=c/5,c1=c%5;
	for(int i=0;i<=4;i++)
		v[i]=vector<int>({0});
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		int x5=(x+4)/5,x1=((-x)%5+5)%5;
		v[x1].push_back(x5);
	}
	for(int i=0;i<=4;i++)
		partial_sum(v[i].begin(),v[i].end(),v[i].begin());
	memset(f[1],0x1f,sizeof(f[1]));
	f[1][0]=0;
	for(int i=1;i<=4;i++)
	{
		if(v[i].size()==0)
			continue;
		// cout<<"i="<<i<<endl;
		memcpy(f[0],f[1],sizeof(f[0]));
		memset(f[1],0x1f,sizeof(f[1]));
		for(int r=0;r<i;r++)
			devideConquer(i,r,r,((4*n-r)/i)*i+r,r,((4*n-r)/i)*i+r);
		// for(int x=4*n;x>=0;x--)
		// 	f[1][x]=min<int>(f[1][x],f[1][x+1]);
		// for(int x=0;x<=4*n;x++)
		// 	cout<<"f "<<i<<" x="<<x<<" = "<<f[1][x]<<endl;
	}
	int ans=0;
	for(int x=0;x<=4*n;x++)
	{
		// cout<<"f "<<x<<" = "<<f[1][x]<<endl;
		if(f[1][x]<=c5)
			ans=x;
	}
	cout<<ans+c1<<endl;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 10036kb

input:

5 57
9 14 31 18 27

output:

8

result:

ok answer is '8'

Test #2:

score: 0
Accepted
time: 4ms
memory: 9992kb

input:

4 50
11 11 11 11

output:

12

result:

ok answer is '12'

Test #3:

score: 0
Accepted
time: 113ms
memory: 10440kb

input:

100000 89648823509660
921733427 402270498 51157221 585477094 435728758 913951087 580580944 557082810 585086423 837912728 799129405 867009344 751591136 714946046 464999915 256043168 416678301 183246216 569365122 479031618 435168577 31068363 903791719 497652990 960987871 223120213 395437892 112869678 ...

output:

200414

result:

ok answer is '200414'

Test #4:

score: -100
Wrong Answer
time: 117ms
memory: 10580kb

input:

99999 3234700062922
394766137 401419056 55997758 205712163 585962152 750591556 245421581 607883471 437707305 758188075 522354844 202404802 307099733 99935245 321784033 643800024 481548024 43007287 404431495 848761213 352455926 541535791 702868758 875691279 485597478 119612707 776231855 48839061 1144...

output:

25636

result:

wrong answer expected '61505', found '25636'