时间限制 1 Second  内存限制  512 Mb

题目描述

给个字符串s和整数k.（字符串中只有0-9）

问至少修改字符串中的几位才可以让字符串的各个位之和大于等于k.

输入

第一行一个整数T表示有T组测试数据 (1 ≤ T ≤ 10)

接下来每组测试数据:

第一行给定一个整数k.

第二行给定字符串s. (1 ≤ strlen(s), k ≤ 1e5)

输出

每组数据输出一行表示最小的修改次数,如果无法满足题意请输出-1.

输入样例

2

5

13

100

123

输出样例

1

-1

思路

这个题的Tag是贪心，但是感觉和贪心没什么关系（可能是我对贪心的理解不够）

思路就是先求出来字符串的长度L，计算字符串所有的字符更改后能达到的最大值（也就是9*L）与k进行比较，如果小于k，那么一定无法达到要求，输出-1

如果大于k，将字符串的各位换成整型存起来，并计算各位数字相加的总和，如果大于k，那么输出0 ，如果小于k，将整型数升序排序，从第一位开始更改（因为题意要求输出最小的修改次数，所以要把小的数变成最大的才能使每一次修改后的总和增加的最大，升序排序会更容易操作一些），记录下来更改的次数输出就可以了

其实上面的这些过程都可以在一起进行（标程也是这样写的），但是用的时间稍微多了一点

AC代码

我自己写的

/**

 * Time: 1ms Memory: 3MB Lang: C++ Author: wzy

 */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#define ll long long

#define ull unsigned long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x7f7f7f7f

#define lson o<<1

#define rson o<<1|1

const double E=exp(1);

const int maxn=1e6+10;

const int mod=1e9+7;

using namespace std;

char ch[maxn];

int a[maxn];

int main(int argc, char const *argv[])

{

	ios::sync_with_stdio(false);

	int t;

	int k;

	cin>>t;

	while(t--)

	{

		cin>>k;

		cin>>ch;

		int l=strlen(ch);

		if(9*l<k)

		{

			cout<<-1<<endl;

			continue;

		}

		int res=0;

		for(int i=0;i<l;i++)

		{

			a[i]=ch[i]-'0';

			res+=a[i];

		}

		if(res>=k)

		{

			cout<<0<<endl;

			continue;

		}

		sort(a,a+l);//升序

		int ans=0;

		for(int i=0;i<l;i++)

		{

			if(a[i]==9)

				continue;

			res=res+9-a[i];

			ans++;

			if(res>=k)

			{

				cout<<ans<<endl;

				break;

			}

		}

	}

	return 0;

}

标程

/**

 * Time: 2ms Memory: 3MB Lang: C++

 */

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll k, g, ans;

string s;

int main() {

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int T; cin>>T;

    while(T--) {

        ans=0,g=0;

        s.clear();

        cin >> k;

        cin >> s;

        for (int i = 0; i < s.length(); i++)

            g += s[i] - '0';

        sort(s.begin(), s.end());

        for (int i = 0; i < s.length(); i++) {

          	if(s[i] == '9') break;

            if (g < k) {

                g += 9 - s[i] + '0';

                ans++;

            }

        }

    if(g<k) cout<< -1<<endl;

    else cout << ans << endl;

    }

    return 0;

}