请大家指点指点关于程序超时问题 - C语言论坛

已结贴√ 问题点数：20 回复次数：20

请大家指点指点关于程序超时问题

题目:
Time Limit: 1000MS
Description
lyl想送给wjh三个礼物，他想送给wjh三个戒指。商场有n个戒指。每个戒指价值v_i。。wjh很挑剔她想要个总价值大于等于k的礼物，而且不要相同的戒指，请问lyl有多少方案送？

Input
（请用scanf读入）
第一行t表示t个样例，1<=t<=100
每个样例
第一行有n和k 表示n个礼物保证 1<=n<=1000 保证 0<=k<=10^16
下一行有n个v_i用空格相隔。表示n个戒指的价值（注意有时不同戒指的价值一样）保证 1<=v_i<=10^15 不保证有序
Output
n行。每一行表示多少种方案。
Sample Input
5
8 5
1 1 1 2 3 4 5 6
4 7
1 2 3 4
2 0
1 1
8 4
1 1 1 1 1 1 1 1
8 3
1 1 1 1 1 1 1 1
Sample Output
52
3
0
0
56

应该是我的算法太差,求指点改改算法

程序代码：

# include <stdio.h>

int main (void)
{
    int t;
    int count;
    int i, j, k;
    int n; 
    long sum;
    long v[1000];
    int num = 0;

    scanf("%d", &t);

    for(count=0; count<t; count++)
    {
        scanf("%d %ld", &n, &sum);              //表示n个礼物,总价值大于sum

        for(i=0; i<n; i++)
        {
            scanf("%ld", &v[i]);      //戒指的价钱
        }

        if(n < 3)
        {
            num = 0;
            printf("%d\n", num);
        }

        else
        {
            num = 0;

            for(i=0; i<n; i++)
            {
                for(j=i+1; j<n; j++)
                {
                    for(k=j+1; k<n; k++)
                    {
                        if((v[i]+v[j]+v[k]) >= sum)
                        {
                            ++num;
                        }
                    }
                }
            }

            printf("%d\n", num);
        }
    }

    return 0;
}

[ 本帖最后由岑吼吼于 2014-5-14 15:56 编辑 ]

搜索更多相关主题的帖子: 礼物　戒指　价值　而且　

第 2 楼

得分:0

给你个建议，不要去计算什么和，
只要计算方案，那用排列组合的知识就可以了。
下班了，等晚上回去了再给你具体的代码。这之前你可以自己试试。

第 3 楼

得分:0

值域为[0, 1]，0代表不买，1代表买就行，约束为>=k。

梦想拥有一台龙芯3A-4000

第 4 楼

得分:0

论坛的一些问题实际上是数学问题，这更应该归于讨论算法的分论坛（没有注意是否有这样的分论坛）。

第 5 楼

得分:0

路过，

编写的程序，不能改变世界，却可以改变自己...

第 6 楼

得分:0

没看太明白

我不是砖家，要努力成为砖家。

第 7 楼

得分:0

回复 2 楼 pangshch

只要计算方案是什么意思呢?没太懂

第 8 楼

得分:0

回复 6 楼砖家的谎言

是我的程序看不明白?还是题目

第 9 楼

得分:0

回复 3 楼 ditg

大神不能很明白你的意思,

第 10 楼

得分:15

二分查找

程序代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX  1000

int comp(const void *a, const void *b)
{
    return *(long long *)b - *(long long *)a;
}

// 在降序数组中找到小于 key 的最大数的 下标
size_t binserch(long long sa[MAX], int n, long long key)
{
    size_t low = 0, high = n - 1, mid;
    if (key == sa[low])
    {
        while (key == sa[low])  low++;
        return low;
    }
    if (key <= sa[high])  return n;
    if (key >  sa[low])   return low;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (key == sa[mid])
        {
            while (key == sa[mid])  mid++;
            return mid;
        }
        if (1 == high - low)  break;
        if (key < sa[mid])  low  = mid;
        if (key > sa[mid])  high = mid;
    }
    return high;
}

int main(int argc, char *argv[])
{
    int       t, n, count;
    long long k, v[MAX];

    for (scanf("%d", &t); t > 0; t -= 1)
    {
        count = 0;
        scanf("%d%lld", &n, &k);
        for (size_t i = 0; i < n; i++)  scanf("%lld", &v[i]);
        qsort(v, n, sizeof(long long), comp);

        size_t a = binserch(v, n, k / 3);
        for (size_t i = 0; i < a && i < n - 2; i++)
        {
            size_t b = binserch(v, n, (k - v[i]) / 2);
            for (size_t j = i + 1; j < b && j < n - 1; j++)
            {
                size_t c = binserch(v, n, k - v[i] - v[j]);
                if (1 + j < c)  count += c - j - 1;
            }
        }
        printf("%d\n", count);
    }

    return 0;
}

[ 本帖最后由 azzbcc 于 2014-5-14 23:36 编辑 ]

[fly]存在即是合理[/fly]