关于#TLE#的问题，如何解决？(关键词-取整)

#求助

/*题目描述
NOI2130即将举行。为了增加观赏性，CCF决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为w%，即当前排名前w%的选手的最低成绩就是即时的分数线。

更具体地，若当前已评出了p个选手的成绩，则当前计划获奖人数为max(1, ?p × w%?)，其中w是获奖百分比，?x?表示对x向下取整，max(x,y)表示x和y中较大的数。如有选手成绩相同，则所有成绩并列的 选手都能获奖，因此实际获奖人数可能比计划中多。

作为评测组的技术人员，请你帮CCF写一个直播程序。

输入格式
第 1 行两个正整数 n, w。分别代表选手总数与获奖率。

第 2 行有 n 个非负整数，依次代表逐一评出的选手成绩。

输出格式
只有一行，包含 n 个非负整数，依次代表选手成绩逐一评出后，即时的获 奖分数线。相邻两个整数间用一个空格分隔。

样例 1 输入
10 60
200 300 400 500 600 600 0 300 200 100
样例 1 输出
200 300 400 400 400 500 400 400 300 300
样例 1 解释
avatar 注意，在第 9 名选手的成绩评出之后，计划获奖人数为 5 人，但由于有并 列，因此实际会有 6 人获奖。

样例 2 输入
10 30
100 100 600 100 100 100 100 100 100 100
样例 2 输出
100 100 600 600 600 600 100 100 100 100
数据范围与提示
avatar

对于所有测试点，每个选手的成绩均为不超过 600 的非负整数，获奖百分比 w 是一个正整数且 1 ≤ w ≤ 99。

在计算计划获奖人数时，如用浮点类型的变量(如 C/C++中的 float、 double，Pascal中的real、double、extended等)存储获奖比例 w%，则计 算 5 × 60% 时的结果可能为 3.000001，也可能为 2.999999，向下取整后的 结果不确定。因此，建议仅使用整型变量，以计算出准确值。

*/
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

int main(){
    int n,w;
    cin>>n>>w;
    int p[n+2];
    int tong[605];
    memset(tong,0,sizeof(tong));
    memset(p,0,sizeof(p));
    for (int i=1;i<=n;i++){
        int sum=0;
        int t=i*w/100;
        int f=max(1,t);
        cin>>p[i];
        tong[p[i]]++;
        for (int j=600;j>=0;j--){
            sum+=tong[j];
            if (sum>=f){
                cout<<j<<" ";
                break;
            }
        }
    }
    return 0;
}

三个TLE！

不知道你这个问题是否已经解决, 如果还没有解决的话:
  • 这篇博客: 2 最长上升子序列及其衍生中的 1）朴素版（容易TLE） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:

     

    #include<bits/stdc++.h>
using namespace std;
const int N=3010;
int a[N],b[N],f[N][N];
int main()
{
  int n,ans=0;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  for(int i=1;i<=n;i++) scanf("%d",&b[i]);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
  {
      f[i][j]=f[i-1][j];//所有不包含a[i]的最长公共上升子序列
      if(a[i]==b[j])//所有包含a[i]的最长公共上升子序列
      {
          f[i][j]=max(f[i][j],1);//当空的时候是自己，也就是1
          for(int k=1;k<j;k++)//求最长公共上升子序列
            if(b[k]<b[j])
                f[i][j]=max(f[i][j],f[i][k]+1);
      }
  }
  //求最大值,第一个序列的前n个字母，与b的匹配最大
  for(int i=1;i<=n;i++) ans=max(ans,f[n][i]);
 printf("%d\n",ans);
    return 0;
}

     

  • 以下回答来自chatgpt:

    我的建议是在代码中尽可能地使用整型运算，这可能会比浮点数运算更快。此外，避免使用除数为小数的操作和带有余数操作（如模运算）。在代码中使用位运算符号（如移位，按位与/或）也可以提高效率。在循环中使用递增变量，而不是递减变量，可以避免在每次迭代中对变量的递减。最后，尝试对算法进行优化，减少无用运算的次数。如果您能提供更具体的代码片段或算法细节，我可以为您提供更个性化的建议。


如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

码字不易，希望得到您的采纳。

这是一道简单的模拟题。首先需要读入 n 和 w，表示选手总数和获奖率。然后按顺序读入每个选手的成绩。每次读入一个成绩后，就按照题目所述计算出当前的获奖分数线，并将其输出。

具体的实现步骤如下：

  1. 读入 n 和 w。

  2. 用一个数组 scores 记录每个选手的成绩。

  3. 用一个变量 p 记录当前已评出的选手数。

  4. 对于每个选手的成绩，计算出当前的获奖分数线：

    a. 将 scores 数组按照从小到大的顺序排序。

    b. 根据当前已评出的选手数 p 和获奖率 w，计算出当前的获奖人数。

    c. 如果当前已评出的成绩中存在相同的，那么将这些成绩全部标记为已获奖，即使它们超出了当前的获奖人数。

    d. 将当前的获奖分数线设置为排序后的 scores 数组中第 min(pw, n) 个成绩。

  5. 将当前的获奖分数线输出。

下面是代码实现：#include
#include
#include
using namespace std;

const int MAXN = 100005;

int n, w;
int a[MAXN];
int ans[MAXN];

int main()
{
    cin >> n >> w;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    sort(a, a + n);

    for (int i = 0; i < n; i++)
    {
        int p = i + 1;
        int cnt = ceil(p * w / 100.0);
        ans[i] = a[cnt - 1];
    }

    for (int i = 0; i < n; i++)
    {
        cout << ans[i] << " ";
    }

    return 0;
}