NC16037. 可乐
描述
输入描述
第一行三个整数n，m，k分别表示要买的可乐数、小美喝的可乐数以及可供选择的可乐种数。
接下来k行，每行两个整数a，b分别表示某种可乐分别给予小美和小团的快乐程度。
对于所有数据，1 <= n <= 10,000, 0 <= m <= n, 1 <= k <= 10,000, -10,000 <= a, b <= 10,000
输出描述
一行k个整数，第i个整数表示购买第i种可乐的数目。
如果有多解，请输出字典序最小的那个。
对于两个序列 a1, a2, ..., ak, b1, b2, ..., bk，a的字典序小于b，当且仅当存在一个位置i <= k满足：
ai < bi且对于所有的位置 j < i，aj = bj；
示例1
输入:
2 1 2 1 2 3 1
输出:
0 2
说明:
一共有三种购买方案：ObjC(gcc 5.4) 解法, 执行用时: 7ms, 内存消耗: 376K, 提交时间: 2018-09-23 23:41:37
#include <stdio.h>
void main()
{
int n,m,k,i,f,sum=-0x3f3f3f3f,a,b;
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
if(sum<=(a*m+b*(n-m)))
{
sum=a*m+b*(n-m);
f=i;
}
}
for(i=1;i<=k;i++)
{
if(i!=f)
printf("0");
else
printf("%d",n);
if(i!=k)
putchar(' ');
}
putchar('\n');
}
Python3(3.5.2) 解法, 执行用时: 50ms, 内存消耗: 4216K, 提交时间: 2020-08-10 01:03:01
n, m, k = [int(i) for i in input().split()]
ans, pos = -1E100, 0
for i in range(k):
a, b = [int(i) for i in input().split()]
tmp = m * a + (n - m) * b
if ans <= tmp:
ans, pos = tmp, i
for i in range(pos): print(0, end=' ')
print(n, end=' ')
for i in range(pos+1, k): print(0, end=' ')
print("")
C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 612K, 提交时间: 2020-02-15 21:20:12
#include<cstdio>
int main()
{
int n,m,k,a,b,t=-1000000000,p;
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<k;i++)
{
scanf("%d%d",&a,&b);
a=a*m+b*(n-m);
if(a>=t) t=a,p=i;
}
for(int i=0;i<k;i++)
{
printf("%d%c",i==p?n:0,i+1==k?10:32);
}
}