2020百度の星初試合二1004 Car

Problem-6778テーマ:いくつかのナンバープレートをあげて、それからナンバープレートの末尾番号によって1週間の平日内に制限して、1種類の末尾番号は1週間に1回しか制限できなくて、あなたに1日に最大何台の車があるかを聞きます.
考え方:最初は欲張りと最小生成樹だと思って、後ろに書いてwaして、後ろに着いて暴力dfsであることを発見して、血を吐く1 e 5のデータ、暴力は過ぎることができます
元のコード、問題がどこにあるか分かりません.

#include
using namespace std;

int turnNum(char a) {
	return a-'0';
}

int main() {
	int o;
	scanf("%d",&o);
	while(o--) {
		int n;
		scanf("%d",&n);
		getchar();
		char a[10];
		int ans[12];
		memset(ans,0,sizeof(ans));
		priority_queue<int> q;
		for(int i=0; i<n; i++) {
			gets(a);
			ans[turnNum(a[4])]--;
		}
		int k = 0;
		for(int i=0; i<10; i++) {
			if(ans[i]!=0) {
				q.push(ans[i]);
//				printf(" %d ",ans[i]);
				k++;
			}
		}
//		printf("K:%d--|%d|--
",k,q.top());
		if(k<5) {
			printf("%d
",n);
		} else {
			while (!q.empty()&&k>5) {
//				printf("--|%d||
",k); 
				int fis = q.top();
				q.pop();
				if (!q.empty()) {
					int sec = q.top();
					q.pop();
					q.push(fis+sec);
				}
				k--;
//				printf("-|%d||
",k);
			}
			int sum = q.top();
			printf("%d
",n+sum);
		}

	}
	return 0;
}

そして暴力のコード(他の人が过ごすことができることを见て、しかしやはりTLEであることを発见して、2点を必要とします):

#include 
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x)
{
    int s = 0, c = getchar();
    x = 0;
    while (isspace(c))
        c = getchar();
    if (c == 45)
        s = 1, c = getchar();
    while (isdigit(c))
        x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    if (s)
        x = -x;
}

template <typename T>
void write(T x, char c = ' ')
{
    int b[40], l = 0;
    if (x < 0)
        putchar(45), x = -x;
    while (x > 0)
        b[l++] = x % 10, x /= 10;
    if (!l)
        putchar(48);
    while (l)
        putchar(b[--l] | 48);
    putchar(c);
}

void DFS(int tot, int cnt[], int sum[], int &ans, int n)
{
    if (tot == 10)
    {
        int qwq = 1e9;
        for (int i = 0; i < 5; ++i)
        {
            qwq = min(qwq, sum[i]);
        }
        ans = min(ans, n - qwq);
        return;
    }
    for (int i = 0; i < 5; ++i)
    {
        sum[i] += cnt[tot];
        DFS(tot + 1, cnt, sum, ans, n);
        sum[i] -= cnt[tot];
    }
}

int main(void)
{
    int kase;
    read(kase);
    for (int ii = 1; ii <= kase; ii++)
    {
        int n;
        read(n);
        int cnt[10] = {0};
        for (int x, i = 1; i <= n; ++i)
        {
            read(x);
            cnt[x % 10]++;
        }
        int ans = 1e9 + 7;
        int sum[5] = {0};
        DFS(0, cnt, sum, ans, n);
        write(ans, '
');
    }
    return 0;
}